python - 如何使用 Python 检测有向图中的循环？

Question

我有一些输入，如:[('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')] .我想在这个 edgeList 表示的有向图中寻找循环是否存在。

我看了一个讨论:https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ ，但是在以下情况下会出现一些错误:

g = Graph(3)
g.addEdge('A', 'B')
g.addEdge('B', 'C')
g.addEdge('C', 'A')

它的结果是“图没有循环”。这显然是错误的。
你能帮我解决这个问题吗？

Answer 1

使用 networkx库，我们可以使用 simple_cycles 函数来查找有向图的所有简单循环。

示例代码:

import networkx as nx

edges = [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]

G = nx.DiGraph(edges)

for cycle in nx.simple_cycles(G):
    print(cycle)

G = nx.DiGraph()

G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'A')

for cycle in nx.simple_cycles(G):
    print(cycle)

输出:

['D', 'C']
['B', 'C', 'A']