Курс Модуль 1: Python Core - Лекция: Алгоритмы поиска в ширину (BFS)

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. Проверка двудольности графа:

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

Применение:

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