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-20 09:59:48Z

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, 2013 at 9:59

answered Nov 20, 2013 at 0:40

Stefan Haustein

18.9k3 gold badges40 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

brain storm Over a year ago

how would this "depthFirstSearch(String name1, String name2)" on recursive happen? pass the name1 and name2 the same?

Stefan Haustein Over a year ago

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?

brain storm Over a year ago

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 Over a year ago

I do not understand how to implement recursion? can you give a little more concrete steps. Thank you

Stefan Haustein Over a year ago

== 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.

|

Collectives™ on Stack Overflow

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

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related