Q
BFS循環檢測
1
A
回答
1
您可以採取非遞歸 DFS算法,您可以用隊列替換節點堆棧以獲得BFS算法。這是簡單的:
q <- new queue // for DFS you use just a stack
append the start node of n in q
while q is not empty do
n <- remove first element of q
if n is visited
output 'Hurray, I found a cycle'
mark n as visited
for each edge (n, m) in E do
append m to q
由於BFS訪問每個節點和每條邊只有一次,你有一個的Ø複雜(| V | + | E |)。
0
我覺得BFS算法非常適合。 時間複雜度是相同的。
你想是這樣的(維基百科編輯):
Cycle-With-Breadth-First-Search(Graph g, Vertex root):
create empty set S
create empty queue Q
root.parent = null
Q.enqueueEdges(root)
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n is not in S:
add n to S
n.parent = current
Q.enqueue(n)
else //We found a cycle
n.parent = current
return n and current
我只添加了其他的週期塊週期檢測和移除探測目標的原始如果達到目標塊。總的來說,它是相同的算法。
要找到確切的週期,你將不得不爲n和當前找到一個共同的祖先。最低的一個可用於O(n)時間。比周期是已知的。祖先對n和當前。電流和n連接。
有關週期和BFS更多信息閱讀此鏈接https://stackoverflow.com/a/4464388/6782134
相關問題
- 1. 檢測循環引用
- 2. 循環內循環 - 在autohotkey中檢測循環結束
- 3. 檢測併發隊列中的循環循環
- 4. 檢測循環有向圖中的多個循環
- 5. 循環引用檢測的LINQ
- 6. 檢測對象中的循環引用
- 7. 使用std :: shared_ptr檢測循環引用
- 8. 跟蹤檢測鏈表中的循環
- 9. 檢測RxUI中的循環引用
- 10. 流星 - 檢測無限循環
- 11. 當出現循環時檢測到
- 12. 檢測循環依賴與Maven
- 13. 問題在Haskell檢測循環次數
- 14. Yosys邏輯循環虛假檢測
- 15. 遊戲循環中的碰撞檢測?
- 16. 檢測鍵無限循環時按下
- 17. C#如何檢測循環引用?
- 18. 繼承中的循環檢測
- 19. for循環檢測連續值
- 20. 可以檢測到無限循環嗎?
- 21. 檢測鏈接列表中的循環
- 22. Python:檢測循環導入的腳本
- 23. 在我的BFS函數中的無限循環
- 24. 在沒有Floyds循環檢測算法的情況下檢測鏈表中的循環
- 25. Granger-循環測試
- 26. 檢索外循環
- 27. 自檢引用循環檢測屬性MVC中的錯誤
- 28. 重複性檢查觸發器錯誤508(循環檢測)
- 29. BFS檢測週期,其中它不應該是
- 30. 如何檢測並保存邊緣頂點的循環連接(孔檢測)?
你爲什麼要使用BFS?你一定要嗎 ? 如果沒有,閱讀此,你可能更喜歡使用DFS:http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs – kazu
@ kazu我想看看它是如何實現的,因爲我的實現被搞砸了。 –
你只需要知道一個循環是否存在或你需要提取特定的圓圈本身? – Codor