Поиск в ширину: алгоритм обхода графа

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

История

Идея систематического обхода графа по уровням впервые была формализована в 1950-х годах в контексте разработки алгоритмов для решения задач на графах. Одним из первых описал метод, аналогичный поиску в ширину, американский математик Эдвард Форрест Мур в 1957 году при работе над алгоритмом нахождения кратчайшего пути в лабиринте (алгоритм Мура). В 1959 году алгоритм был независимо переоткрыт и опубликован американским информатиком Клиффордом Шоу в связи с задачами искусственного интеллекта. В современной формулировке BFS стал стандартным элементом курсов алгоритмов и структур данных, начиная с 1970-х годов, после выхода книги «Искусство программирования» Дональда Кнута.

Описание алгоритма

Принцип работы

Поиск в ширину использует очередь (FIFO — first in, first out) для хранения вершин, которые необходимо посетить. Алгоритм начинает работу с заданной стартовой вершины, помечает её как посещённую и помещает в очередь. Затем, пока очередь не пуста, извлекается первая вершина, и для каждого её соседа, который ещё не был посещён, выполняется: пометка как посещённого, запись расстояния (или предка) и добавление в очередь. Таким образом, сначала обрабатываются все вершины на расстоянии 1 от старта, затем — на расстоянии 2 и так далее.

Псевдокод

`` BFS(граф G, начальная вершина s): для каждой вершины v в G: visited[v] = false distance[v] = ∞ parent[v] = null visited[s] = true distance[s] = 0 очередь Q = пусто Q.enqueue(s) пока Q не пуста: v = Q.dequeue() для каждого соседа u вершины v: если not visited[u]: visited[u] = true distance[u] = distance[v] + 1 parent[u] = v Q.enqueue(u) ``

Сложность

Временная сложность BFS составляет O(V + E), где V — количество вершин, E — количество рёбер графа, при условии, что граф представлен списками смежности. При использовании матрицы смежности сложность возрастает до O(V²). Пространственная сложность — O(V) в худшем случае (для хранения очереди и массива посещённых вершин).

Классификация и варианты

По типу графа

• BFS на неориентированном графе — стандартный случай, алгоритм работает без изменений.
• BFS на ориентированном графе — обход происходит только по направленным рёбрам; расстояния считаются как длина пути по направлению.
• BFS на взвешенном графе — в классической формулировке не применим, так как не учитывает веса рёбер; для взвешенных графов используется алгоритм Дейкстры.

По модификациям

• Двунаправленный поиск в ширину — запускается одновременно из начальной и конечной вершин; позволяет сократить количество просматриваемых вершин в задачах поиска пути.
• BFS с ограничением глубины — обход прекращается после достижения определённого расстояния (k-BFS).
• BFS для поиска компонент связности — многократный запуск BFS из непосещённых вершин позволяет выделить все компоненты связности графа.

Применение

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

BFS гарантированно находит кратчайший путь по числу рёбер между начальной и любой достижимой вершиной. Это свойство используется в:

• навигационных системах (например, в картах метро для поиска минимального числа пересадок);
• маршрутизации в компьютерных сетях (протоколы OSPF, IS-IS используют BFS для построения кратчайших путей);
• решении головоломок (кубик Рубика, игра «15»).

Проверка двудольности графа

BFS можно использовать для проверки, является ли граф двудольным. При обходе вершины окрашиваются в два цвета; если в какой-то момент соседние вершины оказываются одного цвета, граф не двудольный. Этот метод применяется в задачах распределения ресурсов, составления расписаний и анализа социальных сетей.

Построение остовного дерева

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

Поиск компонент связности

В неориентированном графе BFS позволяет выделить все компоненты связности за один проход: после завершения обхода из одной вершины все непосещённые вершины образуют новую компоненту.

Топологическая сортировка

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

Анализ социальных сетей

BFS применяется для вычисления таких метрик, как:

• степень центральности (число соседей);
• близость (среднее расстояние до всех вершин);
• посредничество (доля кратчайших путей, проходящих через вершину).

Искусственный интеллект и игры

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

Примеры

Пример 1: Поиск кратчайшего пути в графе метро

Рассмотрим фрагмент схемы Московского метрополитена. Пусть требуется найти минимальное число пересадок от станции «Красные Ворота» (Сокольническая линия) до станции «Тверская» (Замоскворецкая линия). BFS, запущенный из «Красных Ворот», посетит сначала соседние станции на той же линии («Красные Ворота» — «Чистые пруды» — «Лубянка» — «Охотный Ряд»), затем через пересадку на «Охотном Ряду» на Замоскворецкую линию достигнет «Тверской» за 4 перегона. Результат: кратчайший путь — 4 станции.

Пример 2: Проверка двудольности

Пусть дан граф с вершинами A, B, C, D и рёбрами A-B, B-C, C-D, D-A. BFS, начиная с A, окрашивает A в цвет 1, B — в цвет 2, C — в цвет 1, D — в цвет 2. Ни одно ребро не соединяет вершины одного цвета — граф двудольный. Если добавить ребро A-C, то при обходе A и C окажутся одного цвета, что укажет на недвудольность.

Реализация на языках программирования

Python

```python from collections import deque

def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) distance = {start: 0} parent = {start: None} while queue: v = queue.popleft() for neighbor in graph[v]: if neighbor not in visited: visited.add(neighbor) distance[neighbor] = distance[v] + 1 parent[neighbor] = v queue.append(neighbor) return distance, parent ```

C++

```cpp

include <vector>

include <queue>

include <unordered_map>

std::unordered_map<int, int> bfs(const std::vector<std::vector<int>>& graph, int start) { std::unordered_map<int, int> distance; std::queue<int> q; std::vector<bool> visited(graph.size(), false); visited[start] = true; distance[start] = 0; q.push(start); while (!q.empty()) { int v = q.front(); q.pop(); for (int u : graph[v]) { if (!visited[u]) { visited[u] = true; distance[u] = distance[v] + 1; q.push(u); } } } return distance; } ```

Сравнение с другими алгоритмами

Критика и ограничения

• Неприменимость к взвешенным графам — BFS не учитывает веса рёбер, поэтому для поиска кратчайшего пути по сумме весов требуется алгоритм Дейкстры или A*.
• Высокая пространственная сложность — при большом диаметре графа очередь может содержать значительное число вершин, что критично для ограниченной памяти.
• Отсутствие эвристик — BFS не использует информацию о цели, что делает его неэффективным в больших пространствах состояний (например, в играх с миллионами состояний).
• Не подходит для бесконечных графов — без ограничения глубины BFS может работать бесконечно.

Интересные факты

• BFS является основой для алгоритма поиска кратчайшего пути в протоколе OSPF (Open Shortest Path First), используемом в интернет-маршрутизации.
• В 1990-х годах BFS применялся в программе-решателе кубика Рубика (Kociemba’s algorithm) для нахождения решений с минимальным числом ходов.
• В теории графов BFS используется для вычисления эксцентриситета вершин и радиуса графа.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик Р. Фундаментальные алгоритмы на C++. — СПб.: ДиаСофт, 2002.
• Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2006.
• Moore E. F. The shortest path through a maze // Proceedings of the International Symposium on the Theory of Switching. — Harvard University Press, 1959.
• Russell S., Norvig P. Artificial Intelligence: A Modern Approach. — 4th ed. — Pearson, 2020.