使用寬度優先搜索在圖中找到週期的僞代碼

請給我使用BFS查找循環的僞代碼。我知道這種類型的其他問題存在，但沒有提供代碼。使用寬度優先搜索在圖中找到週期的僞代碼

來源

2010-12-16 Programmer

@ppl：如果您查看我的問題和喜歡，記得投了:) – Programmer 2011-11-09 17:06:44

以防萬一，DFS更適合於任務，在有向圖中更是如此。如果你已經知道這一點，不要理會。

至於僞代碼，在無向圖中，它是一個傳統的BFS，當它到達先前標記爲已訪問的節點時，會中止並報告找到的一個循環。你可以找到BFS here的僞代碼。

在有向圖中，它變得更加棘手，因爲您必須記住當您到達節點時您正在走路的方式，並且與DFS相比，空間複雜度的缺點變得更糟。

編輯：哦，我在談論測試循環圖，而不是實際找到循環。使用DFS查找週期幾乎是微不足道的，而在實際算法複雜性和代碼複雜度方面，使用BFS查找週期要複雜得多。這就是爲什麼你沒有找到僞代碼。

來源

2010-12-16 18:59:16 slezica

爲無向圖，以測試周期存在，我覺得你的解決方案是不正確。考慮：o ---- o – Programmer 2010-12-16 19:25:28

你的意思是K2？我沒有看到問題= S – slezica 2010-12-16 19:26:54

關於您的檢測無向圖中的週期的方法，請考慮2 ---- 1。如果我從1開始BFS，我將開始將它標記爲已訪問並將其添加到隊列中。然後，在while循環中，我將從隊列中檢索它，並將所有相鄰的未訪問頂點標記爲已訪問並將它們添加到隊列中。換句話說，我會在隊列中加2。現在，當我從隊列中檢索2時，我將再次考慮它的所有相鄰頂點。這樣做，我也會考慮已經訪問過的1個。但是，這並不表示一個週期。 – Programmer 2010-12-17 07:11:16

-1

你可能是指DFS，這在循環檢測中更常見，所以我會假設你犯了這個錯誤。雖然核心思想保持不變，但轉向BFS相當容易。

func detectCycle() 
    for node in graph: 
    visited = bool[N] 
    set all visited to false 
    detectCycle(n, n, visited) 

func detectCycle(n, origin, visited) 
    for neighbour in graph[n] 
    if neighbour == origin 
     cycle detected 
    if not visited[neighbour] 
     visited[neighbour] = true 
     detectCycle(neighbour, visited) 
     visited[neighbour] = false

來源

2010-12-16 19:01:46 marcog

我在談論BFS :) – Programmer 2010-12-16 19:33:20

所以，你有沒有BFS的僞碼？ – Programmer 2010-12-18 07:48:48

@編程器：檢查CLRS – phoxis 2012-07-03 12:10:03

使用寬度優先搜索在圖中找到週期的僞代碼

回答

相關問題