Обход в ширину

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

История

Алгоритм обхода в ширину впервые был формально описан в 1959 году американским математиком Эдвардом Фордом в контексте задачи поиска кратчайшего пути в графе. Однако схожие идеи использовались и ранее: например, в работах Леонарда Эйлера по теории графов (XVIII век) и в алгоритмах поиска в лабиринтах, основанных на методе «волнового фронта». В 1961 году алгоритм был независимо переоткрыт и популяризирован в компьютерных науках Робертом Тарьяном и другими исследователями. С развитием вычислительной техники BFS стал одним из базовых алгоритмов, реализуемых в учебных курсах и библиотеках (например, в Boost Graph Library, NetworkX, стандартной библиотеке Python).

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

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

BFS использует очередь (FIFO — «первым пришёл, первым обслужен») для хранения вершин, которые необходимо посетить. Алгоритм начинает с заданной начальной вершины (источника), помечает её как посещённую и помещает в очередь. Затем, пока очередь не пуста, извлекается первая вершина, и для каждого её соседа, который ещё не был посещён, выполняется:

• пометка соседа как посещённого;
• установка расстояния до соседа (равного расстоянию до текущей вершины + 1);
• добавление соседа в очередь.

Таким образом, вершины обрабатываются в порядке возрастания расстояния от начальной: сначала все вершины на расстоянии 1, затем на расстоянии 2 и т.д. Это гарантирует, что при первом достижении вершины будет найдено кратчайшее расстояние (в рёбрах) от источника.

Псевдокод

`` BFS(граф G, вершина start): создать очередь Q создать массив visited, изначально false создать массив distance, изначально INF visited[start] = true distance[start] = 0 Q.push(start) while Q не пуста: v = Q.pop() for each neighbour u of v in G: if not visited[u]: visited[u] = true distance[u] = distance[v] + 1 Q.push(u) return distance ``

Сложность

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

Применение

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

BFS находит кратчайшее расстояние (в количестве рёбер) от начальной вершины до всех остальных. Это свойство используется в навигационных системах (например, в картах метро), в сетевых протоколах (например, OSPF — Open Shortest Path First, хотя там применяются взвешенные алгоритмы), в задачах поиска в социальных сетях (найти кратчайшую цепочку знакомств).

Проверка связности графа

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

Нахождение компонент связности

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

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

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

Двунаправленный поиск

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

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

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

Поиск в лабиринтах и игровых полях

BFS применяется в компьютерных играх для поиска пути (например, в стратегиях реального времени), в задачах робототехники (планирование траектории) и в решении головоломок (например, «пятнашки» или кубик Рубика — в сочетании с эвристиками).

Варианты и модификации

BFS с весами (0-1 BFS)

Если рёбра имеют вес 0 или 1, можно использовать модификацию с деком (двусторонней очередью) вместо обычной очереди. Рёбра с весом 0 добавляются в начало дека, с весом 1 — в конец. Это позволяет сохранить линейную сложность O(|V| + |E|).

Многоисточниковый BFS

Запускается из нескольких начальных вершин одновременно. Используется, например, в задачах «ближайший выход из лабиринта» или при моделировании распространения пожара.

BFS на бесконечных графах

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

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

• Поиск в глубину (DFS): DFS использует стек (или рекурсию) и обходит граф вглубь, не гарантируя кратчайшего пути. BFS, напротив, гарантирует кратчайший путь в невзвешенном графе, но требует больше памяти для хранения очереди.
• Алгоритм Дейкстры: Обобщение BFS для взвешенных графов с неотрицательными весами. BFS является частным случаем алгоритма Дейкстры, когда все веса равны 1.
• Алгоритм A*: Использует эвристическую оценку для ускорения поиска, но не гарантирует оптимальность без допустимой эвристики. BFS проще и не требует эвристик.

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

Python (с использованием списка смежности)

```python from collections import deque

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

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 является одним из немногих алгоритмов, который гарантированно находит кратчайший путь в невзвешенном графе за линейное время.
• В теории графов BFS используется для вычисления эксцентриситета, радиуса и диаметра графа.
• Алгоритм BFS лёг в основу протокола STP (Spanning Tree Protocol) в компьютерных сетях, который предотвращает образование петель в Ethernet-сетях.
• В задачах искусственного интеллекта BFS применяется в качестве базового алгоритма поиска в пространстве состояний, например, в решении головоломки «Ханойская башня» (при ограниченном числе дисков).

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013. — Глава 22.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — М.: Вильямс, 2016. — Глава 4.
• Эдвард Форд. «Flows in Networks». — Princeton University Press, 1962.
• Документация Boost Graph Library: BFS Visitor Concept.