檢測週期在圖

可能重複：
Finding all cycles in graph 檢測週期在圖

有誰能夠給我的教程，算法，...在圖中檢測週期？

我發現幾個算法並加以實施，但沒有檢測到所有周期

2011-03-01 SajjadZare

我想那裏的問題，雖然mared作爲「回答」它沒有正確回答。 – CygnusX1 2011-03-01 21:23:48

@Cygn這不是允許dups的理由。只要去那裏，通過發表意見來「加熱」這個問題，說明 – 2011-03-01 22:22:09

有一個實現來檢測名爲'networkx'的python庫中的圖中的所有周期。 **這真的很簡單！** 我在下面的帖子中給出了詳細的答案：http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/33956957#33956957 – fernandosjp 2016-10-28 14:18:10

從視圖多個數學點：

輸入：圖形G =（V，E）

假設你的圖形是不相交（有每兩個頂點之間存在路徑）
計算spanning tree T中的曲線圖的（有容易的算法來做到這一點）
令E」是的一個子集E，它們不屬於生成樹T.對於E'中的每個邊e，它對樹的添加只產生一個單獨的循環。讓我們把所有這些循環置於集合B中。
我們在圖中定義了一個binary cycle space循環。在該空間中，可以添加兩個循環。加法僅僅是邊緣上的獨佔總和。
循環組B是一個「循環基礎」。在圖形中，每隔一個週期可以形成爲週期的線性組合B.

這樣，你在你的圖獲得所有可能的週期。

警告：如果輸入圖有v頂點和Ë邊緣則有2 ^（Ë - v +1）-1不同的週期！這相當多 - 你可能不想明確地寫出所有這些。

來源

2011-03-01 21:11:59 CygnusX1

-2

我認爲DFS會做你的工作怎麼把我們紀念訪問節點，如果我們發現該節點再有一個週期

來源

2011-03-01 14:28:59 ashmish2

這種方法是不正確的。就拿這個例子 '1 - > 2 2 - > 3 1 - > 3' 現在，在這種情況下，我們做的DFS（1）。這將會調用dfs（2）並將2標記爲已訪問。這將調用dfs（3）並將3標記爲已訪問。現在DFS（3）將再次從節點1調用，因爲它已經訪問了，你會錯誤地推斷，它的一個週期 – 2012-04-03 12:16:58

A BFS alg。也沒關係。我相信它比DFS更容易實現，因爲它將訪問/訪問節點保持在隊列中。檢查某個節點是否已經訪問過很容易。

來源

2011-03-01 19:51:46

檢測週期在圖

回答

相關問題