python - 即使使用队列也无法按广度搜索

Question

我试图理解和实现广度优先搜索。

在这种情况下使用 Queue，因为 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']

Answer 1

您正在使用默认的 pop() 和 append() 函数，它们在队列的同一(右)端运行，这实际上等同于一个堆栈。您可能想要使用的是 popleft() 和 append()，或者 pop() 和 appendleft()。您可以找到列出的一些示例 here .

在您的程序中修复此问题的最短更改是替换

while q:
    u = q.pop()

与

while q:
    u = q.popleft()