Кратчайшие пути: поиск в ширину

Как навигатор находит дорогу, а социальная сеть — «рукопожатия» между людьми? Через поиск в ширину.

Поиск в ширину (BFS) — обход графа по «слоям», который находит кратчайший путь по числу рёбер от стартовой вершины до всех остальных.

Графы описывают дороги, друзей в соцсети, ссылки между страницами. Естественный вопрос — найти кратчайший маршрут. Когда все рёбра «равноценны», задачу решает элегантный алгоритм поиска в ширину.

Идея «волны»

Представьте, что от стартовой вершины расходится волна. Сначала она достигает всех непосредственных соседей (расстояние 1), затем их соседей (расстояние 2) и так далее. BFS обрабатывает вершины именно в таком порядке, используя очередь. Поскольку волна доходит до вершины кратчайшим путём первой, расстояние, записанное при первом посещении, и есть минимальное число рёбер.

Реализация BFS

from collections import deque

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 5],
    5: [3, 4],
}

def shortest_distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

distances = shortest_distances(graph, 0)
for v in sorted(distances):
    print(f"кратчайший путь 0 -> {v}: {distances[v]} рёбер")

Вывод:

кратчайший путь 0 -> 0: 0 рёбер
кратчайший путь 0 -> 1: 1 рёбер
кратчайший путь 0 -> 2: 1 рёбер
кратчайший путь 0 -> 3: 2 рёбер
кратчайший путь 0 -> 4: 2 рёбер
кратчайший путь 0 -> 5: 3 рёбер

Как работает под капотом

Сердце алгоритма — очередь (структура «первым пришёл — первым вышел»). Мы кладём в неё стартовую вершину, затем в цикле вынимаем вершину из начала и добавляем в конец всех её непосещённых соседей, записав им расстояние на единицу больше. Поскольку вершины выходят из очереди в порядке возрастания расстояния, к каждой мы приходим кратчайшим путём первый же раз — повторно её не обновляем (проверка neighbor not in dist). Так BFS гарантированно даёт минимум рёбер. Именно этот алгоритм лежит в основе подсчёта «рукопожатий» в соцсетях: расстояние между двумя людьми — это длина кратчайшей цепочки знакомств.

Частые ошибки

BFS находит кратчайший путь по числу рёбер, но не учитывает «вес» (длину дороги, время): для взвешенных графов нужен алгоритм Дейкстры. Не используйте стек вместо очереди — получится поиск в глубину, который кратчайшесть не гарантирует. И обязательно помечайте посещённые вершины, иначе в графе с циклами алгоритм зациклится.

Итог

BFS обходит граф «волнами» по слоям расстояния.
Находит кратчайший путь по числу рёбер.
Использует очередь и пометки посещённых вершин.
Для взвешенных рёбер нужен Дейкстра, не BFS.