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

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()

Answer 2

对双端队列对象使用 popleft() 而不是 pop()。例如，这就是使用双端队列而不是列表的要点。在您编写的代码中，列表不会有性能问题，但是使用 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']

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

Unable to search by breadth even when using a queue

python

algorithm