8.1 Принципы работы алгоритма BFS
Поиск в ширину (Breadth-First Search, BFS) — это алгоритм обхода или поиска в графе, который начинает с начальной вершины и исследует все её соседние вершины на текущем уровне перед переходом к вершинам следующего уровня.
Шаги алгоритма:
- Начинаем с выбранной начальной вершины и помещаем её в очередь.
-
Пока очередь не пуста, выполняем следующие действия:
- Извлекаем вершину из головы очереди и помечаем её как посещённую.
- Для каждой непосещённой соседней вершины добавляем её в очередь.
- Повторяем шаг 2, пока не будут посещены все вершины, достижимые из начальной вершины.
Визуализация:
Временная сложность:
O(V + E)
, где V
— количество вершин, E
— количество рёбер.
Каждый узел и каждое ребро графа посещаются один раз.
Пространственная сложность:
O(V)
, так как используется очередь для хранения вершин, а также массивы для
хранения состояния (посещённые вершины).
8.2 Реализация BFS с использованием очереди
Обход в ширину хорошо реализуется с помощью такой структуры данных, как очередь.
Реализация BFS с использованием очереди:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex) # Обработка узла
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
# Пример использования:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
bfs(graph, 'A')
8.3 Двунаправленный поиск в ширину
BFS часто используется в играх, когда нужно найти кратчайший путь между двумя точками в сложном ландшафте. Такая задача легко превращается в задачу поиска пути в графе между двумя вершинами. Рёбра такого графа — это все проходимые пути на карте.
Но чтобы найти путь быстрее, его обычно ищут с двух концов. Для этого применяется двунаправленный BFS.
Принцип работы
Двунаправленный поиск в ширину (Bidirectional BFS) — это оптимизированный вариант алгоритма BFS, который выполняет два параллельных обхода графа: один от начальной вершины и другой от целевой вершины. Обходы продолжаются до тех пор, пока два обхода не пересекутся, что значительно сокращает количество проверяемых вершин и рёбер по сравнению с классическим BFS.
Шаги алгоритма:
- Инициализация двух очередей: одна для обхода от начальной вершины, другая — от целевой.
- Инициализация двух множеств посещённых вершин для отслеживания посещённых вершин в обоих направлениях.
- Выполнение попеременного обхода графа из двух очередей.
- При каждом шаге проверяется, пересекаются ли множества посещённых вершин. Если пересечение найдено, путь существует.
- Процесс продолжается до тех пор, пока не будет найден пересекающийся узел или очереди не опустеют.
Временная сложность
В лучшем случае: O(2 * (V + E)) = O(V + E)
, где V
— количество вершин, E
—
количество рёбер.
Двунаправленный BFS обычно выполняет обход меньшего числа вершин по сравнению с однопроходным BFS, особенно в больших графах.
Пространственная сложность:
O(V)
для хранения двух очередей и двух множеств посещённых вершин.
Пример реализации двунаправленного BFS
Пример очень длинный — алгоритм раза в три длиннее, чем однонаправленный поиск — поэтому я приводить его не буду. Когда он вам действительно понадобится, вы будете в состоянии написать его сами.
8.4 Примеры задач, решаемых с использованием BFS
Классические примеры задач, решаемых с использованием BFS:
1. Поиск кратчайшего пути в неориентированном графе:
BFS используется для нахождения кратчайшего пути (минимального количества рёбер) от начальной вершины до целевой в неориентированном графе.
Применение:
- В навигационных системах для нахождения кратчайшего пути между точками.
- В сетевом анализе для нахождения кратчайшего пути передачи данных.
2. Проверка связности графа:
Проверка, является ли граф связным, то есть существует ли путь между любыми двумя вершинами.
Применение:
- В сетевом анализе для проверки связности сети.
- В анализе социальных сетей для проверки связности группы пользователей.
3. Генерация лабиринтов:
Использование BFS для генерации случайных лабиринтов с заданными свойствами.
Применение:
- В игровых приложениях для создания лабиринтов.
- В робототехнике для тестирования алгоритмов навигации.
4. Поиск в ширину в деревьях:
BFS используется для обхода деревьев, чтобы выполнять действия на каждом уровне дерева (например, печать всех узлов на каждом уровне).
Применение:
- В задачах визуализации данных, где требуется отображать данные по уровням.
- В задачах планирования, где требуется выполнение действий на каждом уровне иерархии.
5. Проверка двудольности графа:
Проверка, является ли граф двудольным, то есть можно ли его вершины разбить на два множества так, что рёбра существуют только между вершинами из разных множеств.
Применение:
- В теории графов для проверки двудольности графа.
- В задачах раскраски графов, где необходимо проверить, можно ли раскрасить граф двумя цветами.