java - 多重图中的所有简单路径(深度优先遍历)

Question

阅读和搜索了一段时间后，我仍然无法理解多重图的深度优先遍历(或搜索)(两个顶点可以有多个边)。

我在另一个 SO 问题上找到了这个答案:

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

这是一个很好的答案，但它只适用于简单图。

简而言之，我需要所有简单路径(无重复顶点)在多重图中从顶点 A 到顶点 B，而不仅仅是最短路径。

如果有任何帮助，我将使用 JGraphT 在 Java 中实现它。我不介意使用另一种语言的解决方案。该图是有向的和加权的，如果这也有帮助的话。

附言我不关心算法的运行时间(我会缓存结果)。

我正在寻找类似于链接问题中的输出(我在边缘附加了更多信息，但这与遍历没有太大关系:

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

谢谢。

Answer 1

多重图和普通图实际上不需要不同的代码。在这两种情况下，您都需要知道您过去是否访问过此特定路径 上的给定节点。无论有多少条边可以连接两个顶点，这都有效。

因此，您要做的是，对于每条路径，保留您已经访问过的顶点的列表，并且永远不要前往已经访问过的顶点。因此，一些伪代码:

function DFSHelper(vertex v, array visited):
    for edge in v.edges:
        if edge.vertex_at_end not in visited:
            DFSHelper(edge.vertex_at_end, visited + [edge.vertex_at_end])
    for v in visited:
        print v + "->"

function DFS(vertex v):
    DFSHelper(v, [])

适当调整(例如，这当前打印给定路径的所有子路径，如“A”、“A->B”、“A->B->C”等)。

另请注意，这将打印一些路径两次(如果同一对顶点之间有多个边)。您可以通过在给定函数中仅从顶点 B 移动到顶点 A 一次来进行调整以消除此行为(也就是说，如果多条边连接这两个边，则仅在第一条边上递归，而忽略其余边)。