Алгоритм поиска в ширину (BFS): от теории до реализации с нуля на Python

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

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

Давайте реализуем BFS для графа, представленного в виде списка смежности (adjacency list). Это наиболее гибкое и распространенное представление. Предположим, наш граф ненаправленный и задан словарем, где ключ — вершина, а значение — список смежных вершин.

Шаг 1: Базовый обход. Напишем функцию, которая просто обходит граф и выводит вершины в порядке BFS.
def bfs_basic(graph, start):
 visited = set()  # Множество посещенных вершин
 queue = []  # Очередь (используем список как очередь, но эффективнее использовать collections.deque)
 visited.add(start)
 queue.append(start)
 while queue:
 vertex = queue.pop(0) # Это неэффективно для больших списков! Но для ясности.
 print(vertex, end=' ')
 for neighbor in graph[vertex]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)
Эта реализация проста, но использование `queue.pop(0)` имеет линейную сложность O(n) для списка Python. В реальном коде всегда используйте `collections.deque` с его `popleft()` и `append()` операциями за O(1).

Шаг 2: Поиск кратчайшего пути и расстояний. Чаще всего BFS нужен для нахождения кратчайшего пути. Модифицируем функцию, чтобы она возвращала словарь расстояний от стартовой вершины и словарь "родителей".
from collections import deque
def bfs_shortest_path(graph, start):
 visited = {start}
 queue = deque([start])
 distance = {start: 0}  # Расстояние от start до каждой вершины
 parent = {start: None}  # Родитель вершины в BFS-дереве (для восстановления пути)
 while queue:
 vertex = queue.popleft()
 for neighbor in graph[vertex]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)
 distance[neighbor] = distance[vertex] + 1
 parent[neighbor] = vertex
 return distance, parent
Теперь мы можем найти расстояние до любой достижимой вершины и восстановить сам путь.
def reconstruct_path(parent, target):
 path = []
 node = target
 while node is not None:
 path.append(node)
 node = parent.get(node) # Используем get, так как у start родитель None
 path.reverse()
 return path

Шаг 3: Решение практической задачи — поиск выхода из лабиринта. Представим лабиринт как сетку (двумерный список), где 0 — свободная клетка, 1 — стена. Нам нужно найти кратчайший путь из точки (start_row, start_col) в точку (end_row, end_col). Это классическое применение BFS на графе, где вершины — клетки, а ребра — переходы в соседние по вертикали/горизонтали клетки.
def bfs_maze(maze, start, end):
 rows, cols = len(maze), len(maze[0])
 directions = [(-1,0), (1,0), (0,-1), (0,1)] # Вверх, вниз, влево, вправо
 queue = deque()
 queue.append((start[0], start[1], 0, [start])) # (row, col, distance, path)
 visited = set()
 visited.add(start)
 while queue:
 row, col, dist, path = queue.popleft()
 if (row, col) == end:
 return dist, path # Нашли кратчайший путь и расстояние
 for dr, dc in directions:
 new_row, new_col = row + dr, col + dc
 if (0