Поиск в ширину

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

История

Идея систематического обхода графа с использованием очереди впервые была формализована в середине XX века. В 1959 году американский математик Эдвард Форрест Мур (Edward F. Moore) опубликовал алгоритм, который впоследствии стал известен как поиск в ширину, в контексте задачи поиска кратчайшего пути в лабиринте. Независимо от него, в 1961 году советский математик Александр Алексеевич Зыков в своей монографии «Теория графов» описал аналогичный метод. В 1970-х годах BFS стал стандартным инструментом в программировании после включения в учебники по структурам данных и алгоритмам (например, в работах Дональда Кнута и Роберта Тарьяна). С развитием компьютерных сетей и интернета BFS лёг в основу протоколов маршрутизации и поисковых систем.

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

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

Псевдокод (на неориентированном графе)

`` BFS(граф, начальная_вершина): создать очередь Q создать множество посещённых visited добавить начальную_вершину в Q добавить начальную_вершину в visited пока Q не пуста: v = извлечь первый элемент из Q для каждой вершины u, смежной с v: если u не в visited: добавить u в Q добавить u в visited ``

Временная и пространственная сложность

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

Свойства

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

Применение

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

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

Обход графа и проверка связности

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

Поиск в пространстве состояний

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

Поисковые системы и веб-краулеры

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

Сетевые протоколы

В компьютерных сетях BFS используется в протоколах маршрутизации (например, OSPF — Open Shortest Path First) для построения дерева кратчайших путей. Также алгоритм применяется в протоколе Spanning Tree Protocol (STP) для предотвращения петель в локальных сетях.

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

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

Биоинформатика

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

Разновидности и модификации

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

Вместо одного старта BFS запускается одновременно от начальной и целевой вершин. Алгоритм завершается, когда фронты обхода встречаются. Это сокращает количество просматриваемых вершин в графах с большим разветвлением (например, в социальных сетях). Временная сложность в среднем O(V^(1/2) + E).

Поиск в ширину с весами (0-1 BFS)

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

Поиск в ширину на бесконечных графах

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

Ограничения

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

Реализация на языке Python

Пример простой реализации BFS на неориентированном графе, представленном списком смежности:

```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)

Пример использования

graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } bfs(graph, 'A') # Вывод: A B C D E F ```

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

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

• BFS является частным случаем алгоритма поиска по дереву, где дерево обходится по уровням (level-order traversal).
• В 2012 году группа исследователей из Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) использовала BFS для вычисления среднего расстояния между пользователями социальной сети (около 4,74 шага), что подтвердило гипотезу «тесного мира».
• Алгоритм BFS лежит в основе метода «заливки» (flood fill) в графических редакторах, который заполняет замкнутые области цветом.

Источники

1. Moore, E. F. (1959). «The shortest path through a maze». Proceedings of the International Symposium on the Theory of Switching.
2. Зыков, А. А. (1961). «Теория графов». М.: Наука.
3. Кормен, Т. Х., Лейзерсон, Ч. Э., Ривест, Р. Л., Штайн, К. (2013). «Алгоритмы: построение и анализ» (3-е изд.). М.: Вильямс.
4. Russell, S., Norvig, P. (2020). «Artificial Intelligence: A Modern Approach» (4th ed.). Pearson.
5. Backstrom, L., Boldi, P., Rosa, M., Ugander, J., Vigna, S. (2012). «Four Degrees of Separation». Proceedings of the 4th ACM Web Science Conference.