java - Java中深度优先搜索的递归实现来查找两个节点之间的路径

Question

我正在尝试实现 DFS 的递归版本，以在两个节点之间进行深度优先搜索。这是我的代码。如果存在路径，该方法将返回 true，并且还会更新节点的 prev 字段以跟踪该路径。我已经使用堆栈实现了这种非递归方式，并且工作正常，即 here. 。这个不行。也就是说，它没有给我从节点 A 到节点 B 的路径。它似乎总是返回 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;
}

编辑:经过以下建议，我有了这个代码

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;
        }
        }

对于像这样的给定有向图，

A B
B C
C D
A E
E D 

它能够找到从 A 到 D 的正确路径，但从 A 到仅一个节点的 E 却失败了。

Answer 1

你需要改变

return recursiveDFShelper(v, des);

到

if(recursiveDFShelper(v, des)) {
  return true;
}

否则，您总是在第一次递归调用后从循环中返回。但如果递归没有找到该元素，则需要继续搜索。另一方面，如果您在递归调用中找到了该元素，则希望停止搜索。