Route Between Two Nodes in Graph 176

Question

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

Solution

典型的DFS求解。用stack来实现dfs，用set来记录元素是否曾经被加入过。

代码如下：

/**
 * 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
        if(graph == null || s == null || t == null){
            return false;
        }

        Stack<DirectedGraphNode> stack = new Stack<DirectedGraphNode>();
        HashSet<DirectedGraphNode> set = new HashSet<DirectedGraphNode>();
        stack.push(s);
        set.add(s);

        while(!stack.isEmpty()){
            DirectedGraphNode curt = stack.pop();
            if(curt == t){
                return true;
            }
            for(DirectedGraphNode neighbor : curt.neighbors){
                if(!set.contains(neighbor)){
                    stack.push(neighbor);
                    set.add(neighbor);
                }
            }
        }

        return false;
    }
}