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
DFS:
1 /** 2 * Definition for Directed graph. 3 * class DirectedGraphNode { 4 * int label; 5 * ArrayList<DirectedGraphNode> neighbors; 6 * DirectedGraphNode(int x) { 7 * label = x; 8 * neighbors = new ArrayList<DirectedGraphNode>(); 9 * } 10 * }; 11 */ 12 public class Solution { 13 /** 14 * @param graph: A list of Directed graph node 15 * @param s: the starting Directed graph node 16 * @param t: the terminal Directed graph node 17 * @return: a boolean value 18 */ 19 public boolean hasRoute(ArrayList<DirectedGraphNode> graph, 20 DirectedGraphNode s, DirectedGraphNode t) { 21 // write your code here 22 HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
visited.add(s); 23 return dfs(s, t, visited); 24 } 25 26 public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, HashSet<DirectedGraphNode> visited) { 27 if (s == t) return true; 28 for (DirectedGraphNode neighbor : s.neighbors) { 29 if (!visited.contains(neighbor)) { 30 visited.add(s); 31 if (dfs(neighbor, t, visited)) 32 return true; 33 } 34 } 35 return false; 36 } 37 }
BFS:
1 public class Solution { 2 /** 3 * @param graph: A list of Directed graph node 4 * @param s: the starting Directed graph node 5 * @param t: the terminal Directed graph node 6 * @return: a boolean value 7 */ 8 public boolean hasRoute(ArrayList<DirectedGraphNode> graph, 9 DirectedGraphNode s, DirectedGraphNode t) { 10 // write your code here 11 HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); 12 LinkedList<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>(); 13 if (s == t) return true; 14 queue.offer(s); 15 visited.add(s); 16 while (!queue.isEmpty()) { 17 DirectedGraphNode cur = queue.poll(); 18 for (DirectedGraphNode neighbor : cur.neighbors) { 19 if (neighbor == t) return true; 20 if (visited.contains(neighbor)) continue; 21 visited.add(neighbor); 22 queue.offer(neighbor); 23 } 24 } 25 return false; 26 } 27 }