我正在尝试实现 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 却失败了。
最佳答案
你需要改变
return recursiveDFShelper(v, des);
到
if(recursiveDFShelper(v, des)) {
return true;
}
否则,您总是在第一次递归调用后从循环中返回。但如果递归没有找到该元素,则需要继续搜索。另一方面,如果您在递归调用中找到了该元素,则希望停止搜索。
关于java - Java中深度优先搜索的递归实现来查找两个节点之间的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20105270/