# Route Between Two Nodes in Graph ### Source - lintcode: [(176) Route Between Two Nodes in Graph](http://www.lintcode.com/en/problem/route-between-two-nodes-in-graph/) - [Find if there is a path between two vertices in a directed graph - GeeksforGeeks](http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/) ### Problem Given a directed graph, design an algorithm to find out whether there is aroute between two nodes. #### Example Given graph: ~~~ A----->B----->C \ | \ | \ | \ v ->D----->E ~~~ for `s = B` and `t = E`, return `true` for `s = D` and `t = C`, return `false` ### 題解1 - [DFS](# "Depth-First Search, 深度優先搜索") 檢測圖中兩點是否通路，圖搜索的簡單問題，[DFS](# "Depth-First Search, 深度優先搜索") 或者 [BFS](# "Breadth-First Search, 廣度優先搜索") 均可，注意檢查是否有環即可。這里使用哈希表記錄節點是否被處理較為方便。深搜時以起點出發，遞歸處理其鄰居節點，**需要注意的是處理鄰居節點的循環時不是直接 return, 而只在找到路徑為真時才返回 true, 否則會過早返回 false 而忽略后續可能滿足條件的路徑。** ### Java ~~~ /** * Definition for Directed graph. * class DirectedGraphNode { * int label; * ArrayList<DirectedGraphNode> neighbors; * DirectedGraphNode(int x) { * label = x; * neighbors = new ArrayList<DirectedGraphNode>(); * } * } */ public class Solution { /** * @param graph: A list of Directed graph node * @param s: the starting Directed graph node * @param t: the terminal Directed graph node * @return: a boolean value */ public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) { Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); return dfs(graph, s, t, visited); } public boolean dfs(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited) { if (s == t) { return true; } else { // corner cases if (s == null || t == null) return false; // flag visited node, avoid cylic visited.add(s); // compare unvisited neighbor nodes recursively if (s.neighbors.size() > 0) { for (DirectedGraphNode node : s.neighbors) { if (visited.contains(node)) continue; if (dfs(graph, node, t, visited)) return true; } } } return false; } } ~~~ ### 源碼分析 根據構造函數的實現，Java 中判斷是否有鄰居節點時使用`.size`，而不是`null`. 注意深搜前檢測是否被處理過。行 ~~~ if (dfs(graph, node, t, visited)) return true; ~~~ 中注意不是直接 return, 只在為 true 時返回。 ### 復雜度分析 遍歷所有點及邊，時間復雜度為 O(V+E)O(V+E)O(V+E). ### 題解2 - [BFS](# "Breadth-First Search, 廣度優先搜索") 除了深搜處理鄰居節點，我們也可以采用 [BFS](# "Breadth-First Search, 廣度優先搜索") 結合隊列處理，優點是不會爆棧，缺點是空間復雜度稍高和實現復雜點。 ### Java ~~~ /** * Definition for Directed graph. * class DirectedGraphNode { * int label; * ArrayList<DirectedGraphNode> neighbors; * DirectedGraphNode(int x) { * label = x; * neighbors = new ArrayList<DirectedGraphNode>(); * } * } */ public class Solution { /** * @param graph: A list of Directed graph node * @param s: the starting Directed graph node * @param t: the terminal Directed graph node * @return: a boolean value */ public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) { if (graph == null || s == null || t == null) return false; Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>(); Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); q.offer(s); while (!q.isEmpty()) { int qLen = q.size(); for (int i = 0; i < qLen; i++) { DirectedGraphNode node = q.poll(); visited.add(node); if (node == t) return true; // push neighbors into queue if (node.neighbors.size() > 0) { for (DirectedGraphNode n : node.neighbors) { // avoid cylic if (visited.contains(n)) continue; q.offer(n); } } } } return false; } } ~~~ ### 源碼分析 同題解一。 ### 復雜度分析 時間復雜度同題解一，也是 O(V+E)O(V+E)O(V+E), 空間復雜度最壞情況下為兩層多叉樹，為 O(V+E)O(V+E)O(V+E).