CTCI 4.2

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

CTCI 4.2.java

class Node{
    LinkedList<Node> sons;
    int state;  //0 for unvisited, 1 for visited
}

public boolean hasRoute(Node begin, Node end){
    if(begin == null || end == null) return false;
    if(begin == end) return true;
    
    LinkedList<Node> q = new LinkedList<>();
    begin.state = 1;
    q.add(begin);
    
    while(!q.isEmpty()){
        Node thisNode = q.removeFirst();
        for(Node nextNode : q.sons){
            if(next.state == 0){
                if(next == end) return true;
                else{
                    next.state = 1;
                    q.add(next);
                }
            }
        }
    }
    
    return false;
}