http://www.lintcode.com/en/problem/route-between-two-nodes-in-graph/
https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73092
X. BFS
们也可以采用 BFS 结合队列处理，优点是不会爆栈，缺点是空间复杂度稍高和实现复杂点。
https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/searching/route_between_two_nodes_in_graph.html
Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Example
X. DFS
Given graph:
A----->B----->C
\ |
\ |
\ |
\ v
->D----->E
for
s = B and t = E, return true
for
s = D and t = C, return falsehttps://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73092
检测图中两点是否通路，图搜索的简单问题，DFS 或者 BFS 均可，注意检查是否有环即可。这里使用哈希表记录节点是否被处理较为方便。深搜时以起点出发，递归处理其邻居节点，需要注意的是处理邻居节点的循环时不是直接 return, 而只在找到路径为真时才返回 true, 否则会过早返回 false 而忽略后续可能满足条件的路径。
http://www.cnblogs.com/EdwardLiu/p/5104283.html3 * class DirectedGraphNode { 4 * int label; 5 * ArrayList<DirectedGraphNode> neighbors; 6 * DirectedGraphNode(int x) { 7 * label = x; 8 * neighbors = new ArrayList<DirectedGraphNode>(); 9 * } 10 * };
19 public boolean hasRoute(ArrayList<DirectedGraphNode> graph, 20 DirectedGraphNode s, DirectedGraphNode t) { 21 // write your code here 22 HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); visited.add(s); 23 return dfs(s, t, visited); 24 } 25 26 public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, HashSet<DirectedGraphNode> visited) { 27 if (s == t) return true; 28 for (DirectedGraphNode neighbor : s.neighbors) { 29 if (!visited.contains(neighbor)) { 30 visited.add(s); 31 if (dfs(neighbor, t, visited)) 32 return true; 33 } 34 } 35 return false; 36 }
X. BFS
们也可以采用 BFS 结合队列处理，优点是不会爆栈，缺点是空间复杂度稍高和实现复杂点。
8 public boolean hasRoute(ArrayList<DirectedGraphNode> graph, 9 DirectedGraphNode s, DirectedGraphNode t) { 10 // write your code here 11 HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); 12 LinkedList<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>(); 13 if (s == t) return true; 14 queue.offer(s); 15 visited.add(s); 16 while (!queue.isEmpty()) { 17 DirectedGraphNode cur = queue.poll(); 18 for (DirectedGraphNode neighbor : cur.neighbors) { 19 if (neighbor == t) return true; 20 if (visited.contains(neighbor)) continue; 21 visited.add(neighbor); 22 queue.offer(neighbor); 23 } 24 } 25 return false; 26 }https://codesolutiony.wordpress.com/2015/05/13/lintcode-route-between-two-nodes-in-graph/
用recursive最后一个case会超时，因此用iterative
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) { if (s == t) { return true; } if (graph == null || graph.size() == 0 || s == null || t == null) { return false; } Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); Stack<DirectedGraphNode> stack = new Stack<DirectedGraphNode>(); stack.push(s); while (!stack.isEmpty()) { DirectedGraphNode node = stack.pop(); if (visited.contains(node)) { continue; } visited.add(node); for (DirectedGraphNode neighbor : node.neighbors) { if (neighbor == t) { return true; } stack.push(neighbor); } } return false; }