``` Problem Given a directed graph, design an algorithm to find out whether there is a route between two nodes. Example Given graph: A----->B----->C | | | v ->D----->E for s = B and t = E, return truefor s = D and t = C, return false Note 若s为有向图的终点，经过下一次dfs，会指向null，返回false；否则，只要s所有neighbors的深度搜索中包含满足条件的结果，就返回true。 Solution public class Solution { public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) { Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); return dfs(s, t, visited); } public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited) { if (s == null) return false; if (s == t) return true; visited.add(s); for (DirectedGraphNode next: s.neighbors) { if (visited.contains(next)) continue; if (dfs(next, t, visited)) return true; } return false; } } BFS public class Solution { public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) { if (s == t) return true; Deque<DirectedGraphNode> q = new ArrayDeque<>(); q.offer(s); Set<DirectedGraphNode> visited = new HashSet<>(); while (!q.isEmpty()) { DirectedGraphNode node = q.poll(); visited.add(node); if (node == t) return true; for (DirectedGraphNode child : node.neighbors) { if (!visited.contains(child)) q.offer(child); } } return false; } } ```