CODEWITHSUNDEEP
javadepth-first-search
kaboom
kaboom

Reputation: 833

java depth first search

This is my implementation for the reachable() of a graph using depth first search. It looks for a possible path from vertex 1 (v1) to another vertex (v2) I got some results correctly and some are wrong. I have tried as many ways as I can to debug, but I couldn'd figure out where is wrong. Any help is appreciated. Thank you

public boolean isReachable(V v1, V v2) {
            Stack<V> path = new Stack<V>();
            return isReachableHelper(v1, v2, path);
        }

}

public boolean isReachableHelper(V v1, V v2, Stack<V> path){
        path.push(v1);
        v1.setVisited(true); //set the vertex as being visited

        if (v1.vertex().equals(v2.vertex())){ //check whether vertex' values are equal
            return true;
        }

            //loop through all vertex that are neighbors of v1
        for (V neighbor : super.neighbors(v1)){ 
            if (!neighbor.visited ){ //if the neighbor is not visited before
                return isReachableHelper(neighbor, v2, path); //recursive call
            }
        }

        path.pop(); //no path was found
        return false;
    }

Upvotes: 1

Views: 2549

Answers (1)

tobias_k
tobias_k

Reputation: 82889

The Problem: In your for loop, you only ever expand the first non-visited neighbor node and then immediately return the value of that recursive call. I.e., if no path can be found via the first neighbor of v1, you just 'give up' without looking at the other neighbors.

Instead, you have to try all neighbor nodes until you find one for which the recursive call returns true. In this case, you have found a path and you can return true; otherwise, your method correctly pops the last node from the path and returns false (backtracking).

for (V neighbor : super.neighbors(v1)){ 
    if (!neighbor.visited ){ //if the neighbor is not visited before
        if (isReachableHelper(neighbor, v2, path)) { //recursive call
            return true; // we found a path!
        }
    }
}

Upvotes: 2

Related Questions