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

Question

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.

score 2 · Accepted Answer · answered Nov 21 '13 at 00:36

2

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.

answered Nov 21 '13 at 00:36

Stefan Haustein

18,427
3
36
51

I have another post related to DFS. I think you might be able to help me here: http://stackoverflow.com/questions/20227745/code-for-cycle-detection-is-not-finding-returning-the-right-number-of-cycles-in – brain storm Nov 26 '13 at 20:59

jlars62 · Answer 2 · 2013-11-20T19:49:42.680

0

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.

edited Nov 20 '13 at 19:49

answered Nov 20 '13 at 19:42

jlars62

7,183
7
39
60

do you mean here? `if(!v.isVisited){ sor.prev=v; return recursiveDFShelper(v, des); }` but we have to return false somewhere correct? – brain storm Nov 20 '13 at 20:38

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

2 Answers2

Linked