无法找出 BFS 中的错误

Question

我已经编写了两个版本的 BFS，但是其中一个有一个错误，并且不会导致正确的结果。虽然我无法弄清楚错误是什么。

正确版本：

def find_all_distances(self, start_node):
    distance = {}
    marked = {}
    marked[start_node] = True
    distance[start_node] = 0
    queue = [start_node]
    while queue:
        node = queue.pop(0)
        for adj_node in self.adj[node]:
            if adj_node not in marked:
                marked[adj_node] = True
                distance[adj_node] = distance[node] + 6
                queue.append(adj_node)

错误版本：

def find_all_distances(self, start_node):
    distance = {}
    marked = {}
    queue = [(start_node, 0)]
    while queue:
        node, dist = queue.pop(0)
        marked[node] = True
        distance[node] = dist
        for adj_node in self.adj[node]:
            if adj_node not in marked:
                queue.append((adj_node, dist + 6))

对我来说唯一明显的区别是当我们标记已访问时 - 在添加到队列之前或从队列中弹出之后。为什么这会影响结果？

Answer 1

由于Buggy版本导致相似节点访问两次或以上，示例 :

假设你从 A:

开始

迭代 1：

队列 Q = [A]

已标记 = {}

迭代 2：

节点弹出：A

队列 Q = [B]

已标记 = {A:True}

迭代 3：

节点弹出：B

队列 Q = [C,D]

已标记 = {A:True,B:True}

迭代 4：

节点弹出：C

队列 = [D,D]

已标记 = {A:True,B:True,C:True}

看看发生了什么在第4次迭代中，节点D访问了两次...因为你在弹出后标记节点 .

Answer 2

附带说明一下，pop(0) 的复杂度为 O(n)。不建议使用 Python 列表作为队列。请改用 collections.deque。

无法找出 BFS 中的错误

Unable to figure out the bug in BFS

algorithm

debugging

graph

breadth-first-search