我試圖理解和實施廣度優先搜索。
Queue在這種情況下使用 a因為Stack將用于深度優先搜索。
但是當我列印出結果時，它最終是深度優先而不是廣度。
我錯過了什么？謝謝。
from collections import deque
adj_list = {
'A': ['B', 'D'],
'B': ['A', 'C'],
'C': ['B', 'C'],
'D': ['A', 'E', 'F'],
'E': ['D', 'F', 'G'],
'F': ['D', 'E', 'H'],
'G': ['E', 'H'],
'H': ['G', 'F']
}
q = deque()
visited = {}
level = {}
parent = {}
result = []
for node in adj_list.keys():
visited[node] = False
parent[node] = None
level[node] = float('-inf')
s = 'A'
visited[s] = True
level[s] = 0
q.append(s)
while q:
u = q.pop()
result.append(u)
for v in adj_list[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
level[v] = level[u] 1
q.append(v)
print(result)
這列印：
['A', 'D', 'F', 'H', 'G', 'E', 'B', 'C']
這個結果是深度優先。
首先是廣度，它應該是：
['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']
uj5u.com熱心網友回復：
您正在使用默認pop()和append()函式，它們在佇列的同一（右）端運行，這實際上使其等效于堆疊。您可能想要使用的是popleft()and append(), or pop()and appendleft()。您可以在此處找到一些示例。
在您的程式中解決此問題的最短更改是替換
while q:
u = q.pop()
和
while q:
u = q.popleft()
uj5u.com熱心網友回復：
使用 popleft() 而不是 pop() 作為 deque 物件。例如，這就是使用雙端佇列而不是串列的要點。在您撰寫的代碼中，串列不會有性能問題，但是使用 popleft() 串列需要將所有剩余的元素向左移動一個，這將是低效的（盡管它會給出與使用雙端佇列相同的結果）。deque 資料型別旨在有效地支持這種型別的操作（從集合的左端彈出）。
from collections import deque
adj_list = {
'A': ['B', 'D'],
'B': ['A', 'C'],
'C': ['B', 'C'],
'D': ['A', 'E', 'F'],
'E': ['D', 'F', 'G'],
'F': ['D', 'E', 'H'],
'G': ['E', 'H'],
'H': ['G', 'F']
}
q = deque()
visited = {}
level = {}
parent = {}
result = []
for node in adj_list.keys():
visited[node] = False
parent[node] = None
level[node] = float('-inf')
s = 'A'
visited[s] = True
level[s] = 0
q.append(s)
while q:
u = q.popleft()
result.append(u)
for v in adj_list[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
level[v] = level[u] 1
q.append(v)
print(result)
輸出：
['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463758.html
上一篇：大小為K的有色團的演算法
下一篇：查找給定元素的可能功率計數