创建一个递归寻路算法，查找图中两个节点之间的所有路径

Question

我实现了一个DFS递归算法来查找有向图上两个节点之间的所有路径。目前，我的算法可以找到大约一半的路径(我在一个在线工具上检查了应该有多少条可能的路径)。我不确定我的算法哪里出错了。我检查了一堆不同的帖子，它似乎是别人已经实现的，但我想我可能忽略了一些东西。这是我的第一个寻径算法，我似乎在我的第一个障碍。我不允许使用内置的ADTS，因此建立了我自己的。任何帮助都很感激，因为我真的在这个问题上心烦意乱。如果您需要进一步的信息/代码，请告诉我。

寻路

private void findPaths(String current, String target, LinkedList<String> currPath)
{
Edge edge;
if(current == target)
{
System.out.println(curPath.toString());
return;
}
for (Vertex vertex: current.getAdjacent()))
{
Edge edge = getEdge(current+vertex);
if(!edge.getVisited())
{
edge.setVisited;
curPath.insertLast(vertex);
findPaths(vertex, target, currPath);
curPath.removeLast()
}
}
edge.clearVisited()
}

为便于阅读而编辑。

Answer 1

我认为问题出在这段代码中:

for (Vertex vert1 : current.getVerts())      // say you have 4 unvisited edges
{
label = vert1.toString();
if(!getEdge(current+label).getVisited()) 
{
getEdge(current+label).setVisited(); // you will mark the 4 as visited 
paths.addToPath(label);
findPaths(vert1, target, paths);
paths.removeFromPath();
}
}
getEdge(current+label).clearVisited();      // but unmark only the last one 

你应该用

代替它

for (Vertex vert1 : current.getVerts())
{
label = vert1.toString();
if(!getEdge(current+label).getVisited())
{
getEdge(current+label).setVisited();   // mark this edge
paths.addToPath(label);
findPaths(vert1, target, paths);
paths.removeFromPath();
getEdge(current+label).clearVisited(); // unmark this edge
}
}

或者更简洁，你可以这样重构你的代码:

private void findPaths(Vertex current, String target, Paths<String> paths)
if(current.label.equals(target))
{
System.out.println(paths.getCurrPath());
return;
}
for (Vertex vert1 : current.getVerts())
{
String label = vert1.toString();          // declare&initialize in loop
Edge e = getEdge(current+label);          // lookup only once
if( ! e.getVisited())
{
e.setVisited();
paths.addToPath(label);
findPaths(vert1, target, paths);
paths.removeFromPath();
e.clearVisited();
}
}
}