BFS на Python: поиск кратчайшего пути в графе

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

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

Как работает BFS: интуиция и гарантия кратчайшего пути

Представьте круг на воде от брошенного камня. Первое кольцо касается всех точек на расстоянии 1, второе — на расстоянии 2, и так далее. BFS делает то же самое с помощью очереди: он исследует все узлы на расстоянии k, прежде чем перейти к расстоянию k+1. Из-за этого, когда мы впервые встречаем целевую вершину, мы знаем, что пришли по кратчайшему пути. Если бы существовал более короткий путь, цель появилась бы в более раннем слое.

Формально: пусть d(v) — расстояние от источника до вершины v, найденное BFS. Когда мы извлекаем v из очереди, все вершины с расстоянием d(v)-1 уже обработаны, и ни одна вершина с расстоянием < d(v) не осталась неоткрытой. Следовательно, d(v) минимально.

Сложность: каждая вершина попадает в очередь один раз, каждое ребро просматривается один раз. Итого O(V + E) времени и O(V) памяти — линейно от размера графа.

Пример 1: Кратчайший путь в бинарной матрице (LeetCode 1091)

Дана бинарная матрица n×n. Найдите длину кратчайшего чистого пути из левого верхнего угла в правый нижний, двигаясь только по нулям в 8 направлениях. Если пути нет, верните -1.

До BFS (наивный DFS):

def shortest_path_binary_matrix_bruteforce(grid):
    n = len(grid)
    def dfs(r, c, steps):
        if not (0 <= r < n and 0 <= c < n) or grid[r][c] == 1:
            return float('inf')
        if r == n-1 and c == n-1:
            return steps
        grid[r][c] = 1  # отмечаем посещённым
        best = float('inf')
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == 0 and dc == 0:
                    continue
                best = min(best, dfs(r+dr, c+dc, steps+1))
        grid[r][c] = 0  # возвращаем (backtracking)
        return best
    ans = dfs(0, 0, 1)
    return ans if ans != float('inf') else -1

Этот код работает экспоненциально — на матрице 30×30 он будет выполняться вечность.

После BFS:

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1
    q = deque()
    q.append((0, 0, 1))  # строка, столбец, расстояние
    grid[0][0] = 1  # отмечаем посещённым
    while q:
        r, c, dist = q.popleft()
        if r == n-1 and c == n-1:
            return dist
        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 grid[nr][nc] == 0:
                    grid[nr][nc] = 1  # visited
                    q.append((nr, nc, dist + 1))
    return -1

BFS расширяется уровень за уровнем, гарантируя, что первый раз, когда мы достигаем нижнего правого угла, это кратчайший путь. Никакого экспоненциального взрыва.

Пример 2: Количество островов (LeetCode 200) — вариант BFS

Дана двумерная сетка из '1' (земля) и '0' (вода). Подсчитайте количество островов. Остров окружён водой и образован соединением соседних земель по горизонтали или вертикали.

До BFS (рекурсивный DFS):

def num_islands_dfs(grid):
    def dfs(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

Для больших сеток (например, 10⁴×10⁴) этот код вызовет RecursionError.

После BFS:

from collections import deque

def num_islands_bfs(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(V+E).

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

Выберите одну задачу на графы, которая раньше вызывала трудности — например, «Word Ladder», «Pacific Atlantic Water Flow» или просто лабиринт на бумаге. Попробуйте решить её с помощью BFS. Затем, если хотите, сравните с DFS или Дейкстрой. Опубликуйте своё решение в комментариях — давайте обсудим, у кого получился самый элегантный код. Удачи в поиске кратчайших путей!