## Thursday, September 22, 2016

### LintCode - Route Between Two Nodes in Graph

http://www.lintcode.com/en/problem/route-between-two-nodes-in-graph/
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 `true`
for `s = D` and `t = C`, return `false`
X. DFS
https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73092

http://www.cnblogs.com/EdwardLiu/p/5104283.html
``` 3  * 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>();
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)) {
31                 if (dfs(neighbor, t, visited))
32                     return true;
33             }
34         }
35         return false;
36     }```

X. 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>();
13         if (s == t) return true;
14         queue.offer(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;
22                 queue.offer(neighbor);
23             }
24         }
25         return false;
26     }```
https://codesolutiony.wordpress.com/2015/05/13/lintcode-route-between-two-nodes-in-graph/

`    ``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;`
`    ``}`
https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/searching/route_between_two_nodes_in_graph.html