Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Have you met this question in a real interview?
Yes
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
Analysis:
Set + DFS
/**
* 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) {
// corner cases
if (s == null || t == null) return false;
if (s == t) {
return true;
} else {
// flag visited node, avoid cylic
visited.add(s);
// compare unvisited neighbor nodes recursively
if (s.neighbors.size() > ) {
for (DirectedGraphNode node : s.neighbors) {
if (visited.contains(node)) continue;
if (dfs(graph, node, t, visited)) return true;
}
}
} return false;
}
}