recursive implementation of Depth first search to find path from source to destination in Java

Question

I have this working code for finding path between source to destination non-recursively. I would like to implement recursively, but I am having difficulty in how to do it.

This is my code for non-recursive implementation

public boolean depthFirstSearch(String name1, String name2){
        Vertex source = vertexMap.get(name1);
        Vertex dest = vertexMap.get(name2);
        clearAll();

        Stack<Vertex> stack = new Stack<Vertex>();
        source.setVisited(true);
        stack.push(source);

        while(!stack.isEmpty()){
            source = stack.peek();
            System.out.println(source.name);
            if (dest.name.equals(source.name))
                return true;
            Vertex v = adjacentUnvisitedVertex(source);
            if (v!=null){
                v.setVisited(true);
                v.prev=source;
                stack.push(v);
            }
            else stack.pop();   
        }
        if (!source.name.equals(dest.name)){
            System.out.println("destination cannot be reached");
            return true;
        }
        else return false;
    }

    private Vertex adjacentUnvisitedVertex(Vertex v){

        for (Edge e : v.adj){
            if (!e.target.isVisited){
                return e.target;
            }
        }

       return null;
    }

while a simple DFS recursive implementation is here, that visit all nodes:

static void dfs (Graphnode n) {
   n.setVisited( true );
   Iterator it = n.getSuccessors().iterator();
   while (it.hasNext()) {
      Graphnode m = (Graphnode)it.next();
      if (! m.getVisited()) dfs(m);
   }
}

I would like to implement for finding path between two nodes A and B. so the dfs would take two nodes and find path between recursively.

Thanks

Stefan Haustein · Accepted Answer · 2013-11-20T09:59:48.867

1

The places where you do stack.push() seem to be natural places for the recursive calls. pop() should probably corresponds to returning with false as the result.

But maybe it's more straightforward to convert the recursive dfs() function into the function you need:

Convert dfs() to your target data structure (Graphnode -> Vertex, Iterator... -> while(adjacentUnvisitedVertex(...) etc.). Check if it works with System.out.println(). This might be the hardest part. If you get stuck there, post the output here.
Just add a dest parameter and the check if the nodes match (return true in this case, false after the loop otherwise). Make sure you check the result of the recursive dfs() call in the loop and return true if it has found the element.

edited Nov 20 '13 at 09:59

answered Nov 20 '13 at 00:40

Stefan Haustein

18,427
3
36
51

how would this "depthFirstSearch(String name1, String name2)" on recursive happen? pass the name1 and name2 the same? – brain storm Nov 20 '13 at 00:56
I'd put the recursion in a separate helper method that takes `Vertex` `source` and `dest` arguments. You don't want to do the one-time setup including `clearAll()` in the recursive method. BTW: Why do you do `dest.name.equals(source.name)` instead of just `dest == source`? – Stefan Haustein Nov 20 '13 at 01:02
doing dest==source checks for identity right..but I think here it should not matter. in fact, the vertex need not have to have equals methods implemented correct? – brain storm Nov 20 '13 at 01:54
I do not understand how to implement recursion? can you give a little more concrete steps. Thank you – brain storm Nov 20 '13 at 01:55
== is faster than equals, and the right thing to do if you intend check for identity. What does it mean that nodes are equal? Don't they have to be identical anyway because of the connections? Re: More concrete steps: I have added some details to the answer above. – Stefan Haustein Nov 20 '13 at 10:00
Thanks for pointing out. I tried to implement the recursive version. But I do not have it working. I have posted it here in SO.http://stackoverflow.com/questions/20105270/recursive-implementation-of-depth-first-search-to-find-path-between-two-nodes-in can you look at it when you have time. – brain storm Nov 20 '13 at 19:35
looks good, i think now you just need to chech the return value of the recursive call and return immediately if it is true – Stefan Haustein Nov 20 '13 at 20:40
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/41572/discussion-between-user1988876-and-stefan-haustein) – brain storm Nov 21 '13 at 00:31

recursive implementation of Depth first search to find path from source to destination in Java

1 Answers1

Linked