Databases
StackOverflow2013
Postsdbo
POrecursive implementation of depth first search to find path between two nodes in Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POrecursive implementation of depth first search to find path between two nodes in Java
    primarykey
    data
    text
    <p>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 <a href="https://stackoverflow.com/questions/20084632/recursive-implementation-of-depth-first-search-to-find-path-from-source-to-desti">here.</a>. 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.</p> <pre><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){ if (!sor.name.equals(des.name)){ sor.setVisited(true); Iterator&lt;Edge&gt; 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; } </code></pre> <p>EDIT: After below suggestions, I have this code</p> <pre><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&lt;Edge&gt; 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; } } </code></pre> <p>for a given directed graph like this,</p> <pre><code>A B B C C D A E E D </code></pre> <p>it is able to find the correct path from A to D, but fails from A to E which is just one node away.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USbrain storm
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POrecursive implementation of depth first search to find path between two nodes in Java
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POrecursive implementation of depth first search to find path between two nodes in Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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