[LintCode] Route Between Two Nodes in Graph [DFS/BFS]

NO IMAGE

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 true
for 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;
}
}