python - 如何使用 Python 和 Networkx 在图中找到循环关系？

Question

考虑我有以下图表：

A -> B
B -> C
C -> D
C -> A

找到 A -> B -> C -> A 是循环关系的最简单方法是什么？NetworkX 或其他易于使用的 Python 库中是否已经内置了这样的功能？

Answer 1

networkx.simple_cycles为你做这个。

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> G.add_edge('C', 'D')
>>> G.add_edge('C', 'A')
>>> nx.simple_cycles(G)
[['A', 'B', 'C', 'A']]

Answer 2

使用深度优先搜索来检测图中的循环。