使用BFS循環檢測

我試圖在有向圖中檢測具有BFS算法的循環。我檢測週期的主要思想是：因爲BFS僅訪問每個節點（和邊）一次，如果我再次遇到已經訪問過的節點;它會導致一個循環。但是，我的代碼有時會找到循環，有時候不會。使用BFS循環檢測

的僞代碼，我從維基百科修改低於：

1 procedure BFS(G,v): 
2  create a queue Q 
3  enqueue v onto Q 
4  mark v 
5  while Q is not empty: 
6   t <- Q.dequeue() 
7   if t is what we are looking for: 
8    return t 
9   for all edges e in G.adjacentEdges(t) do 
12    u <- G.adjacentVertex(t,e) 
13    if u is not marked: 
14     mark u 
15     enqueue u onto Q 
16    else: 
17     print "Cycle detected!" //since we saw this node before

我缺少什麼？

來源

2013-01-24 Serra Cordova

當您想要檢測週期時是否遍歷所有節點？ – keyser

從哪裏得到't'，因爲它不是簽名過程的一部分BFS（G，v）：' –

您給出的算法可能會在找到該循環之前找到目標節點（並因此退出）。

哪一個對你更重要：儘快找到目標還是找到循環？如果你不關心目標，你可以刪除算法的那部分。

來源

2013-01-24 19:31:41

你的實現的問題是它假定圖形已連接。但事實是，你可能會處理一個有兩個連接部分的圖表，所以如果你從v開始，你將永遠不會進入其他部分。要解決您的問題，您需要找到一種方法來識別可能未連接的子圖。

實際上是一個簡單的改變就可以使是不是入隊v，排隊的所有節點Dijkstra style：這裏只講

S ← Set of all nodes with no incoming edges

編輯您可能會發現在維基百科http://en.wikipedia.org/wiki/Topological_sorting#Algorithms一些建議。這樣你應該總能找到你的週期。另外你從哪裏得到t，因爲它不是方法簽名的一部分？

來源

2013-01-25 13:09:35

即使沒有循環存在，您給出的算法也可能會報告循環的存在。在第12行中，我們有你在t附近。在BFS樹中t的一個父親也位於它的鄰接表中。 So, line 13 might return false even when no cycle exist because a parent of t is marked and is a part of t's adjacency list.

所以，我覺得，如果它存在，但它也可能報告一個週期，即使是沒有的，該算法將報告週期。

來源

2013-03-17 18:55:19 Jatin

使用BFS循環檢測

回答

相關問題