# Route Between Two Nodes in Graph

## Question

### Problem Statement

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

## 题解1 - DFS

### 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
// 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;
}
}


### 源码分析

if (dfs(graph, node, t, visited)) return true;


## 题解2 - BFS

### 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;

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();
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;
}
}