Determining if there is a route between two nodes in a directed graph

Question

This algorithm should return a boolean value, telling if there is a path between two nodes in a given directed graph.

public enum State{
    White, Grey;
}

public class Node {
    State state = State.White;
    List<Node> neighbors = new ArrayList<Node>();
    //Assumption: Every node already knows about its direct adjacents
    public List<Node>getAdjacent(){ return neighbors;}
}

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst))return true;

        }
    }
    return false; //NO path found
}

What do you think about the concept of it? What are the advantages of of an iterative solution?

Answer 1

You don't reset the src.state when you return the result.

This means that between isThereAPath calls you need to reset the state manually. Instead you should reset the state:

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                src.state = State.White;
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst)){
                src.state = State.White;
                return true;
            }

        }
    }
    return false; //NO path found
}

Answer 2

Style: avoid one-liners such as public List<Node>getAdjacent(){ return neighbors;}