Поиск в ширину (BFS): кратчайший путь в графе

Почему BFS — ваш главный инструмент для графов

Вы когда-нибудь застревали на задаче про лабиринт или поиск кратчайшего пути? Многие разработчики сначала пробуют наивный поиск в глубину и блуждают по тупикам, пока не натыкаются на решение. Но есть способ, который гарантирует кратчайший путь в невзвешенном графе — это поиск в ширину (BFS). В этой статье вы поймёте, почему BFS работает именно так, увидите рабочие примеры на Python и узнаете, как избежать типичных ошибок.

Суть BFS: как волна от камня

Представьте, что вы бросили камень в пруд. Волны расходятся равномерно: каждая точка на расстоянии k достигается раньше, чем точка на расстоянии k+1. BFS делает то же самое с помощью очереди:

1. Начните с исходной вершины и пометьте её как посещённую.
2. Поместите исходную вершину в очередь.
3. Пока очередь не пуста, извлеките переднюю вершину, исследуйте всех её соседей и добавьте в очередь непосещённых, сразу помечая их.

Благодаря тому, что мы обрабатываем вершины в порядке их обнаружения, мы обходим все вершины на расстоянии 0, затем на расстоянии 1, потом 2 и так далее. Когда мы впервые достигаем целевой вершины, мы точно знаем, что прошли минимальное число рёбер — любой другой путь был бы не короче.

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

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

Рассмотрим классическую задачу: дан невзвешенный граф, найдите длину кратчайшего пути между двумя вершинами. Вот простой пример на Python:

from collections import deque

def bfs_shortest_path(graph, start, target):
    if start == target:
        return 0
    visited = set([start])
    q = deque([(start, 0)])  # (вершина, расстояние от старта)
    while q:
        node, dist = q.popleft()
        for neigh in graph.get(node, []):
            if neigh == target:
                return dist + 1  # нашли!
            if neigh not in visited:
                visited.add(neigh)
                q.append((neigh, dist + 1))
    return -1  # целевая вершина недостижима

Почему это работает: очередь хранит вершины в порядке увеличения расстояния. Когда мы впервые видим target, связанное с ним dist — минимальное число рёбер.

Частая ошибка №1: забываем помечать вершину при добавлении в очередь

Если помечать вершину как посещённую только при извлечении, вы можете добавить её в очередь несколько раз через разных родителей. Это раздувает очередь и может привести к повторным посещениям позже, чем истинное кратчайшее расстояние. Решение — как в коде выше: помечайте вершину сразу при добавлении в очередь.

Частая ошибка №2: использование списка как очереди

# НЕ ДЕЛАЙТЕ ТАК
queue = [start]
while queue:
    node = queue.pop(0)  # O(n) сдвиг!

В Python pop(0) сдвигает все элементы, превращая алгоритм из O(V+E) в O(V²). Использование collections.deque даёт O(1) для извлечения слева, сохраняя линейное время.

Ещё один классический пример: «Количество островов»

Задача: подсчитать количество отдельных островов в двумерной сетке, где '1' — суша, '0' — вода. BFS отлично подходит: каждый раз, когда мы находим непосещённую клетку суши, запускаем BFS для заливки острова, увеличиваем счётчик и продолжаем.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r, c):
        q = deque([(r, c)])
        visited.add((r, c))
        while q:
            x, y = q.popleft()
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                nx, ny = x+dx, y+dy
                if 0 <= nx < rows and 0 <= ny < cols \
                   and grid[nx][ny] == '1' and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    q.append((nx, ny))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                islands += 1
                bfs(r, c)
    return islands

Тот же принцип: обход уровень за уровнем, пометка посещённых сразу, гарантия однократной обработки каждой клетки.

Где BFS незаменим

Вооружившись BFS, вы сможете решать огромный пласт задач на графах: кратчайшие пути в невзвешенных графах, проверка двудольности, поиск компонент связности, минимальное число ходов в головоломках, поиск кратчайшей последовательности преобразований слов (классическая задача «hit-cog»).

Вне собеседований BFS — основа многих реальных систем: веб-краулеры (обход ссылок по уровням), алгоритмы рекомендаций друзей в соцсетях (люди, которых вы можете знать через общих знакомых), навигация, когда все дороги имеют одинаковую стоимость.

Красота в том, что когда вы поймёте суть — эффект волны — вы перестанете заучивать код и начнёте видеть паттерны. Вы заметите, когда задача сводится к «найти первый момент достижения X», и поймёте, что BFS — правильный инструмент.

Практическое задание

Теперь, когда у вас есть суперспособность BFS, попробуйте:

Задача: Дано бинарное дерево, верните его минимальную глубину (количество узлов на кратчайшем пути от корня до ближайшего листа). Решите её с помощью BFS и поделитесь решением в комментариях.

Если застрянете, вспомните, что дерево — частный случай графа, где дети узла — его соседи. Удачи в кодинге, и пусть ваши очереди всегда будут полны перспективных узлов!