Алгоритми пошуку в ширину (BFS)

8.1 Принципи роботи алгоритму BFS

Пошук в ширину (Breadth-First Search, BFS) — це алгоритм обходу або пошуку в графі, що починає з початкової вершини і досліджує всі її сусідні вершини на поточному рівні перед переходом до вершин наступного рівня.

Кроки алгоритму:

1. Починаємо з обраної початкової вершини і поміщаємо її в чергу.
2. Поки черга не порожня, виконуємо наступні дії:
   • Виймаємо вершину з голови черги й позначаємо її як відвідану.
   • Для кожної невідвіданої сусідньої вершини додаємо її в чергу.
3. Повторюємо крок 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. Перевірка двошаровості графа:

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

Застосування:

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