如何在Python和Networkx的圖表中找到循環關係？

Question

考慮，我有以下圖表：

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

什麼是發現，一個最簡單的方法 - 「乙 - 」ç - > 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

使用Depth-First Search來檢測圖中的週期。