CODEWITHSUNDEEP
javarecursionpathdepth-first-search
brain storm
brain storm

Reputation: 31242

recursive implementation of depth first search to find path between two nodes in Java

I am trying to implement the recursive version of DFS for depth first search between two nodes. Here is my code. The method will return true if there is a path that exists and it also updates the prev field of the node to keep track of the path. I have implemented this non-recursive way using stacks and it works fine which is here.. This one is not working. That is it is not giving me the path from Node A to Node B. It always seem to return false.

public boolean recursiveDFS(String start, String end){
  clearAll();
  Vertex source = vertexMap.get(start);
  Vertex dest = vertexMap.get(end);
  clearAll();

  return recursiveDFShelper(source,dest);
}

private boolean recursiveDFShelper(Vertex sor, Vertex des){
  if (!sor.name.equals(des.name)){
    sor.setVisited(true);
    Iterator<Edge> it = sor.adj.iterator();

    while (it.hasNext()){
      Vertex v = it.next().target;

      if(!v.isVisited){
        sor.prev=v;
        recursiveDFShelper(v, des); 
      }
    }
    return false;
  }
  else 
    return true;
}

EDIT: After below suggestions, I have this code

public boolean recursiveDFS(String start, String end){
        clearAll();
        Vertex source = vertexMap.get(start);
        Vertex dest = vertexMap.get(end);
        clearAll();

        return recursiveDFShelper(source,dest);

    }

    private boolean recursiveDFShelper(Vertex sor, Vertex des){
        //System.out.println(sor.name);

        if (!sor.name.equals(des.name)){
        sor.setVisited(true);
        System.out.println(sor.adj);
        Iterator<Edge> it = sor.adj.iterator();
        while (it.hasNext()){
            Vertex v = it.next().target;
            if(!v.isVisited){
                v.prev=sor;
                System.out.printf("prev of %s is %s\n",sor,sor.prev);
                return recursiveDFShelper(v, des);  
                }
            }
        //System.out.println("returning false");
        return false;
        }
        else {
           System.out.println("returning true");
           return true;
        }
        }

for a given directed graph like this,

A B
B C
C D
A E
E D

it is able to find the correct path from A to D, but fails from A to E which is just one node away.

Upvotes: 1

Views: 6085

Answers (2)

Stefan Haustein
Stefan Haustein

Reputation: 18793

You need to change 

return recursiveDFShelper(v, des);

to 

if(recursiveDFShelper(v, des)) {
  return true;
}

Otherwise, you always return from the loop after the first recursive call. But you need to continue searching if the recursion did not find the element. On the other hand, if you have found the element in the recursive call, you want to stop the search.

Upvotes: 2

jlars62
jlars62

Reputation: 7353

Well, the problem in your code is that the only time you are going to return true is when the sor and des parameters are equal on the first call to the recursive function, otherwise you are always returning false.

So to fix this, inside recursiveDFShelper, you need to return the result of your recursive call.

Upvotes: 0

Related Questions