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

Почему BFS гарантирует кратчайший путь в графе

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

Что такое BFS и как он работает

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

Ключевой элемент BFS — очередь. Когда мы извлекаем вершину, мы добавляем всех её непосещённых соседей в конец очереди. Это гарантирует, что вершины, обнаруженные раньше (с меньшим расстоянием), обрабатываются раньше. Если бы мы использовали стек (как в DFS), мы бы углублялись, прежде чем проверить соседние вершины, поэтому DFS не может гарантировать оптимальность в невзвешенных графах.

Реализация BFS на Python: пример с бинарной матрицей

Рассмотрим классическую задачу с LeetCode (1091): найти длину кратчайшего пути в бинарной матрице n×n, где 0 — свободная клетка, 1 — препятствие. Двигаться можно в 8 направлениях. Если путь отсутствует, вернуть -1.

Наивный DFS-подход исследует все возможные маршруты, часто посещая одну и ту же клетку множество раз. В худшем случае это экспоненциальная сложность — O(4^(n²)), что неприемлемо для собеседований.

Вот эффективное решение на BFS:

from collections import deque

def shortest_path_bfs(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1
    q = deque()
    q.append((0, 0, 1))  # (строка, столбец, расстояние)
    visited = [[False] * n for _ in range(n)]
    visited[0][0] = True
    while q:
        r, c, d = q.popleft()
        if r == n-1 and c == n-1:
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == 0 and dc == 0:
                    continue
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not grid[nr][nc] and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc, d + 1))
    return -1

Сложность этого решения — O(n²), так как каждая клетка попадает в очередь максимум один раз, и мы проверяем её 8 соседей.

Подсчёт островов с помощью BFS

Ещё одна классическая задача — подсчёт количества островов в двумерной сетке (LeetCode 200). BFS отлично подходит для заливки областей.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                q = deque([(r, c)])
                grid[r][c] = '0'  # помечаем как посещённую
                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':
                            grid[nx][ny] = '0'
                            q.append((nx, ny))
    return islands

Здесь каждая клетка обрабатывается не более одного раза, поэтому время работы — O(rows × cols), а память для очереди в худшем случае — O(min(rows, cols)).

Где применять BFS в реальной жизни

• Поиск пути в играх — персонаж перемещается по лабиринту, BFS даёт оптимальное число ходов без сложных эвристик.
• Социальные сети — поиск кратчайшей цепочки знакомств между двумя людьми (классическая задача «шести рукопожатий»).
• Веб-краулеры — обход в ширину позволяет сначала обнаруживать страницы, ближайшие к стартовому URL, что полезно для соблюдения политик.

Как только вы поймёте, почему очередь обеспечивает порядок по расстоянию, вы сможете адаптировать BFS для взвешенных графов (например, 0-1 BFS) или для бесконечных пространств состояний.

Практический вывод: начните применять BFS прямо сейчас

Возьмите задачу «Кратчайший путь в бинарной матрице» и решите её самостоятельно, не подглядывая в решение. Сначала реализуйте BFS, затем, если захотите, попробуйте алгоритм Дейкстры и сравните время выполнения. Когда вы увидите, как BFS возвращает точное количество шагов, вы почувствуете ту самую магию алгоритмов. Удачи в кодинге, и пусть ваши очереди всегда будут полны перспективных узлов!