CODEWITHSUNDEEP
javaalgorithmrecursiondepth-first-search
orange14
orange14

Reputation: 381

Depth First Search to find all paths between nodes issue

I have been trying to fix this Depth First Search problem but I cant figure it out. I want to print all paths but somehow it only prints some paths. I can figure out the mistake here for such a long time: 

  void printAllPathsUtil(Vertex v, Vertex d, ArrayList<Vertex> path){

        v.state = VISITED;
        path.add(v);

        if (v == d) {
            for (Vertex p : path) {
                System.out.print("Print: " + p.value + " ");
            }
            System.out.println();
        }
        else {
            for (Vertex city : v.outboundCity){

                if (city.state == UNVISITED) {

                    printAllPathsUtil(city, d, path);
                }
            }
        }
        path.remove(v);
        v.state = UNVISITED;
    }


    void printAllPaths(Vertex v, Vertex u){
        clearStates();
        ArrayList<Vertex> path = new ArrayList<>();
        printAllPathsUtil(v, u, path);
    }

Vertex Class is something like this: 

public class Vertex{
String value;

Vertex previous = null;
int minDistance = Integer.MAX_VALUE;

List<Vertex> inboundCity;
List<Vertex> outboundCity;
State state;
}

Upvotes: 1

Views: 109

Answers (1)

Schidu Luca
Schidu Luca

Reputation: 3947

I think you should have this two lines inside the loop:

path.remove(v);
v.state = UNVISITED;

You should remove vertexes from path and "unvisit" them right after your recursion is terminated, not when you end the loop

Upvotes: 1

Related Questions