Route Between Two Nodes in Graph
Source
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
Java
public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
if (graph == null || s == null || t == null) return false;
Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>();
Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
q.offer(s);
while(!q.isEmpty()){
DirectedGraphNode node = q.poll();
visited.add(node);
if(node==t) return true;
for(DirectedGraphNode neighbor: node.neighbors){
if(visited.contains(neighbor)) continue;
q.offer(neighbor);
}
}
return false;
}
}