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

Question

我已经实现了 DFS 递归算法来查找有向图上两个节点之间的所有路径。目前，我的算法正在寻找大约一半的总路径（我在在线工具上检查了应该有多少可能的路径）。我不确定我的算法哪里出错了。我检查了很多不同的帖子，这似乎是其他人已经实现的，但我想我可能忽略了一些东西。这是我的第一个寻路算法，我似乎正在克服我的第一个障碍。我不允许使用内置的 ADTS，因此构建了我自己的。感谢您提供任何帮助，因为我真的很想解决这个问题。如果您需要更多信息，请告诉我 information/code.

寻路

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

}

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

Creating a recursive path finding algorithm to find all paths between two nodes in a graph

java

path-finding

depth-first-search