BFS для чайников: как обходить графы вширь и находить кратчайший путь

Зачем вам BFS? Реальный провал на собеседовании

Помните момент, когда вы пытались найти кратчайший путь в сетке 1000×1000 с помощью рекурсивного DFS? Я тоже через это прошёл: стек переполнялся, экспоненциальный рост ветвлений, а тесты падали с ошибкой. Оказалось, что задача — это поиск кратчайшего пути в невзвешенном графе, и нужен был не глубокий спуск, а волновой обход — слой за слоем. Именно тогда BFS (поиск в ширину) стал моим секретным оружием.

Как работает BFS: аналогия с каплей на воде

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

Код: два классических примера

1. Количество островов (LeetCode 200)

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

Проблема DFS: на больших сетках рекурсия может превысить лимит. Решение — BFS с явной очередью.

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def bfs(sr, sc):
        q = deque()
        q.append((sr, sc))
        grid[sr][sc] = '0'  # помечаем посещённым
        while q:
            r, c = q.popleft()
            for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    grid[nr][nc] = '0'
                    q.append((nr, nc))

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

Время O(V+E), память O(min(V,E)). Никаких проблем со стеком.

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

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

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
                    q.append((nr, nc, dist + 1))
    return -1

Первое достижение цели — минимальное расстояние. Время O(n²), память O(n²).

Типичные ошибки и как их избежать

• Забывать помечать вершины посещёнными при добавлении в очередь. Иначе возможны бесконечные циклы и дублирование работы.
• Использовать список с pop(0) в качестве очереди. Каждый pop(0) стоит O(n), превращая O(V+E) в O(V²+VE). Всегда используйте collections.deque.
• Путать взвешенные и невзвешенные графы. BFS даёт кратчайший путь только если все рёбра равны по весу. Если веса разные — нужен алгоритм Дейкстры.

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

BFS — не просто инструмент для собеседований. Это ментальная модель для задач, где информация распространяется равномерно: рекомендации друзей, веб-краулеры, поиск пути в играх. Как только вы научитесь видеть мир как слои волн, очередь станет вашим первым инстинктом. Возьмите задачу, которую вы откладывали — например, «Гниющие апельсины» или «Тихий океан — Атлантика» — и решите её с помощью BFS. Вы удивитесь, как элегантно и быстро работает этот подход.