Route Between Two Nodes in Graph

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




/**

 * 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) {

        // write your code here

        Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();

        return dfs(s, t, visited);

        

    }

    

    private boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited){

            if(s == null) return false;

            if(s.equals(t)) return true;

            visited.add(s);

            for(DirectedGraphNode n : s.neighbors){

               if(visited.contains(n)) continue;

               if(dfs(n, t, visited)) return true;

            }

        return false;

    }

}

/**

 * 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) {

        // write your code here

        Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();

        Stack<DirectedGraphNode> stack = new Stack<DirectedGraphNode>();

        stack.push(s);

        while(!stack.isEmpty()){

            DirectedGraphNode node = stack.pop();

            if(node.equals(t)) return true;

            if(visited.contains(node)) continue;

            for(DirectedGraphNode n : node.neighbors){

                stack.push(n);

            }

        }

        return false;

    }

}