BFS на графе: кратчайший путь в невзвешенном графе с восстановлением

В прошлом уроке DFS отвечал на вопрос о достижимости, но первый найденный им путь не обязан быть кратчайшим. Теперь нужно минимизировать число рёбер и восстановить сам путь. Для этого вершины придётся обрабатывать по расстоянию от источника.

Инварианты dist[] и parent[]: структура данных BFS на графе

До обхода зафиксируем контракт результата. BFS строит два словаря: dist и parent.

dist[v] — минимальное число рёбер от источника s до вершины v. До старта это число неизвестно для всех вершин, кроме самого источника. Поэтому начальное состояние такое: dist[s] = 0, а для всех остальных вершин dist[v] = -1. Значение -1 играет роль «ещё не открыта» — sentinel, который одновременно сигнализирует, что вершина не достигнута, и служит условием для проверки при обходе.

parent[v] — вершина, из которой v была впервые обнаружена. В начале parent[v] = None для всех вершин, включая s. Для источника parent[s] так и останется None — это маркер конца цепочки при восстановлении пути.

Оба значения записываются до помещения вершины в очередь, а не при извлечении. Как только dist[v] перестаёт быть -1, вершина считается открытой и больше не добавляется.

Входной контракт урока: adj содержит ключ для каждой вершины, каждый сосед также является ключом, а источник s входит в adj. Для графов с вершинами 0..n-1 удобно использовать списки: dist = [-1] * n, parent = [None] * n. Если метки произвольные — строки, кортежи, любые hashable-объекты — переходим на словари с теми же начальными значениями:

dist   = {v: -1   for v in adj}
parent = {v: None for v in adj}
dist[s] = 0

Семантика при этом не меняется. dist[v] всегда означает длину кратчайшего пути в рёбрах, parent[v] — через кого эта длина достигнута.

Итеративный BFS через deque: процедура и сложность

collections.deque с append справа и popleft слева реализует FIFO-очередь с операциями O(1). Этот порядок сохраняет неубывание расстояний при обработке вершин.

from collections import deque

def bfs(adj, s):
    dist   = {v: -1   for v in adj}
    parent = {v: None for v in adj}
    dist[s] = 0

    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if dist[v] == -1:          # вершина ещё не открыта
                dist[v]   = dist[u] + 1
                parent[v] = u
                dq.append(v)
    return dist, parent

Проследим работу на графе с вершинами 0–5 и рёбрами (0,1),(0,2),(1,3),(2,3),(3,4),(4,5), источник s=0.

Шаг 1. deque=[0], dist={0:0}, остальные -1.

Шаг 2. Извлекаем 0. Соседи: 1 и 2 — оба не открыты. Записываем dist[1]=1, parent[1]=0, dist[2]=1, parent[2]=0, добавляем оба. deque=[1,2].

Шаг 3. Извлекаем 1. Сосед 3 не открыт: dist[3]=2, parent[3]=1. deque=[2,3].

Шаг 4. Извлекаем 2. Соседи: 0 (dist=0, пропускаем) и 3 (dist=2, уже открыт — пропускаем). deque=[3].

Шаг 5. Извлекаем 3. Сосед 4: dist[4]=3, parent[4]=3. deque=[4].

Шаг 6. Извлекаем 4. Сосед 5: dist[5]=4, parent[5]=4. deque=[5].

Шаг 7. Извлекаем 5. Нет необработанных соседей. Очередь пуста.

На шаге 4 вершина 3 уже имеет dist[3]=2, поэтому при обработке вершины 2 она пропускается. Каждая вершина попадает в очередь не более одного раза.

Сложность. Инициализация dist и parent просматривает все V ключей. Каждая достижимая вершина добавляется и извлекается один раз. Каждое ребро достижимой части неориентированного графа просматривается дважды, по одному разу с каждой стороны. Поэтому время ограничено O(V + E). Словари dist и parent занимают O(V), очередь — не более O(V).

Корректность BFS: почему первое открытие даёт кратчайший путь

BFS расширяет достигнутую часть по уровням: сначала открывает вершины на расстоянии 1, затем на расстоянии 2 и так далее. Это следует из FIFO-порядка.

Формально: когда вершина u извлекается из очереди с dist[u] = d, все вершины с расстоянием меньше d уже извлечены и полностью обработаны. Это доказывается индукцией по d. Значит, в момент, когда мы смотрим на соседа v вершины u, любой путь до v длиной меньше d+1 уже должен был открыть v раньше — и тогда dist[v] уже не равно -1. Если же dist[v] == -1, значит более короткого пути не существует, и d+1 — это и есть оптимум.

Вот почему запись dist[v] = dist[u] + 1 при первом обнаружении корректна: мы гарантированно нашли кратчайший путь до v именно в этот момент.

Рассмотрим вариант, где dist[v] не устанавливается при добавлении, а отметка откладывается до извлечения:

def bfs_mark_on_dequeue(adj, s):
    """Намеренно ошибочный момент отметки — пример для разбора."""
    visited = set()
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if v not in visited:
                dq.append(v)
        visited.add(u)  # слишком поздно: дубли уже могли попасть в очередь
    return visited

Пусть вершины u1 и u2 находятся на одном уровне и обе смежны с v. После обработки u1 вершина v уже стоит в очереди, но всё ещё отсутствует в visited. Поэтому u2 добавит её повторно. Если дубли не отбрасывать при извлечении, соседи v также будут обработаны повторно; если отбрасывать, лишние элементы всё равно уже попали в очередь. В обоих вариантах доказательство одного enqueue на вершину и времени O(V + E) больше неприменимо. Момент фиксации parent[v] также перестаёт быть однозначным первым открытием.

Корректный порядок: проверить dist[v] == -1, сразу записать dist[v] и parent[v], затем выполнить dq.append(v).

Гарантия относится к невзвешенному графу, где каждое ребро увеличивает длину пути на 1. Рёбра с различными весами требуют другого порядка обработки и выходят за границы этого урока.

Восстановление кратчайшего пути обратным проходом по parent[]

Функция восстановления получает dist и parent, построенные BFS из источника s, а цель t должна быть ключом обоих словарей. Путь собирается в обратном направлении: от t по parent[node] к s.

def reconstruct_path(dist, parent, s, t):
    if dist[t] == -1:
        return []          # t недостижима из s
    path = []
    node = t
    while node != s:
        path.append(node)
        node = parent[node]
    path.append(s)
    path.reverse()
    return path

Разберём граничные случаи.

dist[t] == -1 — вершина t не была достигнута BFS. Возвращаем пустой список: пути не существует.

s == t — условие node != s сразу ложно; после цикла в path добавляется s. Результат равен [s].

Общий случай. Для каждой открытой вершины v != s выполняется dist[parent[v]] = dist[v] - 1. Поэтому при каждом переходе по parent расстояние строго уменьшается и через dist[t] шагов достигает s; цикл в родительской цепочке невозможен. После разворота получаем путь [s, ..., t].

Проверим на нашем примере. После BFS с источником 0: parent = {0:None, 1:0, 2:0, 3:1, 4:3, 5:4}. Восстанавливаем путь до вершины 5:

node=5 → path=[5],      parent[5]=4
node=4 → path=[5,4],    parent[4]=3
node=3 → path=[5,4,3],  parent[3]=1
node=1 → path=[5,4,3,1],parent[1]=0
node=0 → условие node != s ложно; добавляем 0

До разворота path=[5,4,3,1,0]; после reverse() получаем [0, 1, 3, 4, 5]. Длина пути — 5 вершин и 4 ребра, что совпадает с dist[5] = 4.

Сложность восстановления. Цикл делает dist[t] переходов по родителям, после чего в список отдельно добавляется источник. В path находится dist[t] + 1 вершина, а reverse() проходит по ним один раз. Итого O(dist[t] + 1), что не превышает O(V). Дополнительная память — O(dist[t] + 1) под список path.

Вместе BFS и восстановление дают полное решение: O(V + E) на обход и O(V) на память, с гарантией оптимальности найденного пути.