Breadth-First Search

«За сколько ходов конь дойдёт до клетки», «какое минимальное число замен превращает одно слово в другое», «сколько шагов до выхода из лабиринта» — во всех случаях путей экспоненциально много, и перебирать их бессмысленно.

Обход в глубину задачу тоже не решает: он найдёт какой-нибудь путь, но не кратчайший, — и это самая частая подмена на собеседовании, потому что на маленьких тестах результат часто совпадает.

Дисциплина «первым пришёл — первым вышел» держит этот порядок сама: очередь никогда не отдаст вершину дальнего слоя раньше, чем закончится ближний.

       A
      / \
     B   C
    / \
   D   E

слой 0:  A
слой 1:  B C
слой 2:  D E

Вершины B и C помечены посещёнными в момент добавления в очередь, а не в момент извлечения. Поэтому на третьем шаге C не добавляет соседей повторно и очередь не раздувается.

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])

    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u in dist:            # уже посещена или уже в очереди
                continue
            dist[u] = dist[v] + 1
            parent[u] = v            # для восстановления пути
            queue.append(u)

    return dist, parent

• Время — $O(V+E)$: каждая вершина извлекается один раз, каждое ребро просматривается один раз.
• Память — $O(V)$: в очереди в худшем случае лежит целый слой.
• Предусловие — стоимость всех переходов одинакова; иначе это Дейкстра.
• Путь восстанавливается по parent — от цели к старту, затем разворачивается.

Индукция по слоям. Пусть все вершины на расстоянии $k$ уже извлечены в порядке очереди и получили верные расстояния. Их соседи, ещё не помеченные, находятся ровно на расстоянии $k+1$: ближе они быть не могут (иначе были бы помечены раньше), дальше — тоже (есть путь через соседа). Очередь отдаёт их только после всех вершин слоя $k$, значит порядок сохраняется и на следующем слое.

Отсюда же правило пометки. Если помечать вершину при извлечении, она успеет попасть в очередь столько раз, сколько у неё соседей: на плотном графе очередь раздувается до $O(E)$ вместо $O(V)$. Обход останется корректным, но память вырастет — и на разреженных тестах это незаметно, поэтому ошибка доживает до продакшена.

• Пометка при извлечении вместо добавления. Очередь раздувается; на плотном графе это переполнение памяти.
• Разные веса рёбер. Обход в ширину даст неверный ответ — молча.
• Неполный ключ состояния. Если вершина — кортеж, в посещённые кладётся кортеж целиком, иначе обход срежет правильный путь.
• Границы сетки. Проверять их нужно до обращения к клетке, а не после.
• Список вместо очереди. list.pop(0) в Python стоит $O(n)$ — обход становится квадратичным без единой ошибки в логике.

1. Почему вершину нужно помечать при добавлении в очередь, а не при извлечении?
2. Граф, где все рёбра весят 1, кроме одного веса 5: что вернёт обход в ширину и почему это неверно?
3. Мультистарт: чем расстояния при нескольких источниках отличаются от расстояний от одного?
4. Лабиринт с ключами и дверями: что здесь является вершиной?
5. Как восстановить сам путь, а не только его длину?