Невозможно выяснить ошибку в 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

Для примечания, pop(0) имеет сложность O (n). Не рекомендуется использовать список Python в качестве очереди. Вместо этого используйте collections.deque.

Answer 2

Поскольку версия 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 посещался дважды ... потому что вы отмечаете узлы после выхода .