BFS для поиска кратчайшего пути: полное руководство

Зачем осваивать BFS?

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

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

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

Секрет BFS — очередь (FIFO). Мы помещаем стартовый узел в очередь, затем повторяем:

• Извлекаем первый узел из очереди
• Помещаем в очередь всех его непосещённых соседей
• Помечаем соседей как посещённые

Обрабатывая узлы в порядке их обнаружения, мы гарантируем послойное расширение. Время работы: O(V+E), где V — количество вершин, E — количество рёбер.

BFS в действии: примеры кода на Python

Задача «Количество островов»

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

from collections import deque

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0
    visited = [[False] * cols for _ in range(rows)]
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                islands += 1
                queue = deque([(r, c)])
                visited[r][c] = True
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in directions:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and not visited[nr][nc]:
                            visited[nr][nc] = True
                            queue.append((nr, nc))
    return islands

Почему BFS лучше рекурсивного DFS? Нет риска переполнения стека на больших сетках. Каждая ячейка посещается один раз: O(m×n) времени, O(min(m,n)) дополнительной памяти для очереди.

Задача «Лестница слов» (Word Ladder, LeetCode 127)

Даны beginWord, endWord и список допустимых слов. Найдите длину кратчайшей последовательности превращений, меняя по одной букве за шаг. Каждое промежуточное слово должно быть в списке.

from collections import deque, defaultdict

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    L = len(beginWord)
    # Словарь: обобщённое состояние -> список слов
    all_combo = defaultdict(list)
    for word in wordList:
        for i in range(L):
            generic = word[:i] + '*' + word[i+1:]
            all_combo[generic].append(word)
    
    queue = deque([(beginWord, 1)])
    visited = {beginWord: True}
    while queue:
        current_word, level = queue.popleft()
        for i in range(L):
            generic = current_word[:i] + '*' + current_word[i+1:]
            for word in all_combo[generic]:
                if word == endWord:
                    return level + 1
                if word not in visited:
                    visited[word] = True
                    queue.append((word, level + 1))
            # Очищаем, чтобы не обрабатывать повторно
            all_combo[generic] = []
    return 0

Ключевая идея: построение «обобщённых состояний» (например, h*t) сокращает генерацию соседей. BFS гарантирует, что первая встреча endWord даёт минимальное число шагов. Время: O(N×L), где N — количество слов, L — длина слова.

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

• Использование стека вместо очереди. Вы получите DFS, который не гарантирует кратчайший путь. Помните: очередь = FIFO.
• Забыли пометить узел посещённым при добавлении в очередь. Это приводит к повторной обработке и бесконечным циклам. Отмечайте visited сразу после enqueue.
• Рекурсия для больших сеток. Используйте явную очередь, чтобы избежать переполнения стека.

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

Попробуйте самостоятельно решить следующую задачу: дана сетка 2D с 0 (пусто) и 1 (препятствие). Найдите минимальное количество шагов от левого верхнего угла до правого нижнего, двигаясь вверх/вниз/влево/вправо и имея возможность удалить не более одного препятствия. Это вариация BFS с дополнительным состоянием — флагом «использовал ли я удаление?». Удачи!