如何从边列表生成循环列表？

Question

我有一个全连接图中的边列表，其中每条边都表示为它连接的两个节点的元组。我想枚举图中所有可能的循环。

3 节点图示例：给定：

[(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]

想要生成：

[
     [(0,1),(1,0)],
     [(0,2),(2,0)],
     [(1,2),(2,1)],
     [(0,1),(1,2),(2,0)],
     [(0,2),(2,1),(1,0)]
 ]

并不是说循环中边的顺序无关紧要，即
[(0,1),(1,0)] 和 [(1,0),(0,1)] 表示相同的循环。

我尝试使用 itertools 生成循环但没有成功。

Answer 1

该算法是一种改进的深度优先搜索。当到达先前访问过的顶点时，将应用 Dijkstra 算法来查找是否存在形成最短环路的路径。

听起来直截了当，但有很多问题

有向图比无向图更容易，无向图需要额外的检查以防止错误循环在同一条边上来回移动
从不同的顶点开始，可以多次找到一个循环。有必要检查每个循环是否新颖，而不是重复。（我注意到在你的例子中你包含了两次 0-1-2 循环，方向相反。如果这真的是你想要的，那么你可以忽略这一点）
您想处理具有多个组件的图形吗？如果是这样，则需要在未访问的顶点重新启动 DFS，直到访问了所有顶点。

作为参考，这里有一些实现此功能的 C++ 代码：https://github.com/JamesBremner/PathFinder/blob/412c81b79d9f1a9cc91b61293050f93c51522ab1/src/GraphTheory.cpp#L310-L429 您可能想将其移植到 Python，但是我不推荐它——在有大量节点的图上，Python 会非常慢。