Алгоритм поиска в ширину¶

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

¶История

Идея поиска в ширину впервые была формализована в 1950-х годах в контексте исследования лабиринтов и задач искусственного интеллекта. Одним из ранних упоминаний является работа Эдварда Мура (1959), который предложил алгоритм для поиска кратчайшего пути в лабиринте. В 1961 году Клод Шеннон использовал BFS в программе для игры в шахматы. Впоследствии алгоритм стал стандартным компонентом курсов по алгоритмам и структурам данных, а его реализация вошла в учебники Кормена, Лейзерсона, Ривеста и Штейна.

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

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

¶Пример на графе

Рассмотрим неориентированный граф с вершинами A, B, C, D, E и рёбрами: A-B, A-C, B-D, C-E. Если начать обход с вершины A:

1. Очередь: [A]. Посещённые: {A}.
2. Извлекаем A. Соседи: B, C. Добавляем B и C. Очередь: [B, C]. Посещённые: {A, B, C}.
3. Извлекаем B. Соседи: A (уже посещён), D. Добавляем D. Очередь: [C, D]. Посещённые: {A, B, C, D}.
4. Извлекаем C. Соседи: A (посещён), E. Добавляем E. Очередь: [D, E]. Посещённые: {A, B, C, D, E}.
5. Извлекаем D. Соседи: B (посещён). Очередь: [E].
6. Извлекаем E. Соседи: C (посещён). Очередь пуста. Обход завершён.

Порядок обхода: A, B, C, D, E.

¶Реализация

¶Псевдокод

`` BFS(граф G, начальная вершина s): создать пустую очередь Q Q.enqueue(s) отметить s как посещённую пока Q не пуста: v = Q.dequeue() для каждого соседа u вершины v: если u не посещена: Q.enqueue(u) отметить u как посещённую (опционально) записать предка u = v для восстановления пути ``

¶Реализация на Python

```python from collections import deque

def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) ```

¶Реализация на C++

```cpp

¶include <queue>

¶include <vector>

¶include <iostream>

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

¶Свойства

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

¶Применение

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

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

¶Поиск в лабиринтах и на картах

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

¶Обход веб-страниц (краулеры)

Поисковые системы (например, Google) используют BFS для обхода гиперссылок: начиная с заданного набора URL, алгоритм последовательно переходит по ссылкам на каждой странице, собирая новые адреса.

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

BFS применяется для вычисления центральности по близости (closeness centrality) и для поиска сообществ (например, алгоритм Лувена использует BFS на начальном этапе).

¶Тестирование двудольности графа

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

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

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

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

В простых играх (например, «пятнашки» или «судоку») BFS используется для поиска решения при небольшом пространстве состояний. Однако из-за экспоненциального роста числа состояний BFS редко применяется в сложных играх.

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

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

¶Ограничения

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

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

• BFS является основой для алгоритма «поиска в ширину с ограничением глубины» (iterative deepening depth-first search, IDDFS), который сочетает преимущества BFS и DFS.
• В компьютерных сетях BFS используется в протоколах маршрутизации (например, OSPF) для распространения информации о топологии.
• В теории графов BFS применяется для вычисления диаметра графа (максимального расстояния между вершинами).

¶Источники

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