StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POrecursive implementation of Depth first search to find path from source to destination in Java
text
Body
copied!<p>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.</p> <p>This is my code for non-recursive implementation</p> <pre><code>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; } </code></pre> <p>while a simple DFS recursive implementation is here, that visit all nodes:</p> <pre><code>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); } } </code></pre> <p>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.</p> <p>Thanks</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload