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

深さ優先検索を使用して、グラフ内のサイクルを検出します。