在图中找到所有的闭合回路

Question

我正在尝试编写Python代码，以识别任意图形中的所有闭环。

所谓闭环，我指的是一个循环，该循环访问每个顶点不超过一次（除了循环起始点之外的顶点）。在此 图片 中，如DGHD，BCDB或BCEFDB等均为示例。

我曾尝试使用矩阵乘法来完成这个任务。将图形写成矩阵，其中两个顶点之间连接则为1，否则为0，并将其提高到n的幂，但这将考虑非闭合循环。

这位用户似乎也有同样的工作，但他已经解决了：

• 在封闭图中查找唯一循环

我想知道是否有关于应该采取哪个方向的建议？

- Tweej

Answer 1

NetworkX 是一个流行的 Python 包，用于处理图形，在许多科学 Python 发行版中都包含了它。它包括一些计算图形循环的算法。特别是 simple_cycles(DiGraph) 可以回答你的问题。

这种方法的一个注意点是，你必须将你的图形转换成有向图。这意味着你无向图的每条边在有向版本中都会变成一个循环。（一个无向边变成两个有向边。）你可以简单地过滤输出，只包含长度大于三的循环。

以下是使用你提供的图形的示例：

from networkx import Graph, DiGraph, simple_cycles

# construct a graph using a dict: {node:[connected_nodes]}
G = Graph(
    {'A':['B','G','H'],
     'B':['A','C','D'],
     'C':['B','D','E'],
     'D':['B','C','E','F','G', 'H'],
     'E':['C','D','F'],
     'F':['D','E','G'],
     'G':['A','D','F','H'],
     'H':['A','D','G'],
    }
)

# optional: draw the graph for verification
#labels = dict(zip(G.nodes(),G.nodes()))
#networkx.draw_networkx(G,labels=labels)

# simple_cycles only accepts DiGraphs. convert G to a bi-directional
# digraph. note that every edge of G will be included in this list!
DG = DiGraph(G)
list(simple_cycles(DG))

（截断的）输出如下：

[['B', 'D', 'H', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'G', 'A'],
 ['B', 'D', 'H', 'A', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'A'],
 ['B', 'D', 'F', 'E', 'C'],
 ['B', 'D', 'G', 'F', 'E', 'C'],
 ...
]

如果您不想使用NetworkX，可以自己实现此功能，使用Johnson算法的simple_cycles()。 （参见Donald B. Johnson，“Finding All the Elementary Circuits of a Directed Graph”，SIAM J. Comput。，4（1），77-84）

- Chris Swierczewski

---

天啊，我忘记了这个问题。太棒了，我能够使用这个包并得到我需要的东西！非常感谢您的帮助。 - Tweej

NetworkX实现的原始源代码：https://github.com/networkx/networkx/blob/master/networkx/algorithms/cycles.py#L109和一个不错的无依赖版本：https://github.com/qpwo/python-simple-cycles/blob/master/johnson.py - theonlygusti