Route Between Directed Graph
Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Think
- Most typical Graph algorithm question!
- Try two ways: DFS, BFS.
Solution
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
*/
// BFS
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
if(s == t)
return true;
Queue<DirectedGraphNode> queue = new LinkedList<>();
queue.offer(s);
graph.remove(s);
while(!queue.isEmpty()) {
DirectedGraphNode cur = queue.remove();
graph.remove(cur);
for(DirectedGraphNode next : cur.neighbors) {
if(!graph.contains(next))
continue;
if(next == t)
return true;
queue.offer(next);
}
}
return false;
}
// DFS
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
// write your code here
if(s == t)
return true;
for(DirectedGraphNode next : s.neighbors) {
if(hasRoute(graph, next, t))
return true;
}
return false;
}
}