CODEWITHSUNDEEP
javaalgorithmgraphgraph-algorithmdepth-first-search
Whizzil
Whizzil

Reputation: 1364

Test if there is a route between 2 nodes in a graph

I know there are already similar questions, but I would like my searching method to be evaluated. I used a DFS algorithm to find out whether or not there is a route between the two nodes. Here is my code, and I would like to know the if there is a test-case in which my code would fail with the result.

public boolean routeExists(Node start, Node end) {
    Set<Node> visited = new HashSet<>();
    Stack<Node> stack = new Stack<>();

    visited.add(start);
    stack.push(start);

    while(!stack.isEmpty()) {
        Node current = stack.pop();

        if(current.getValue() == end.getValue()) {
            return true;
        }

        for(Node adj : current.getAdjacent()) {
            // keep track of visited nodes
            if(!visited.contains(adj)) {
                stack.push(adj);
                visited.add(adj);
            }
        }
    }

    return false;
}

I have made an EDIT, now the code keeps track of the visited nodes, and does not expand them if they have been visited in the past. I believe this now should work.

Upvotes: 2

Views: 209

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

This code will go into an infinite loop for many input graphs.

Consider finding a route from A to B when the edges are:

A->B
A->C
C->A

Your code will first push B on the list, then push C, then visit C and push A on the list, and then repeat until a stack overflow occurs.

If you compare with wikipedia

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

you will see that you are missing the test to check that the new vertices have not already been discovered.

Upvotes: 4

Related Questions