Algorytmy przeszukiwania wszerz (BFS)

8.1 Zasady działania algorytmu BFS

Przeszukiwanie wszerz (Breadth-First Search, BFS) — to algorytm przeszukiwania lub przeszukiwania grafu, który zaczyna od wierzchołka początkowego i bada wszystkie jego sąsiednie wierzchołki na bieżącym poziomie, zanim przejdzie do wierzchołków następnego poziomu.

Kroki algorytmu:

1. Zaczynamy od wybranego wierzchołka początkowego i umieszczamy go w kolejce.
2. Dopóki kolejka nie jest pusta, wykonujemy następujące czynności:
   • Wyciągamy wierzchołek z przodu kolejki i oznaczamy go jako odwiedzony.
   • Dla każdego nieodwiedzonego sąsiada dodajemy go do kolejki.
3. Powtarzamy krok 2, aż zostaną odwiedzone wszystkie wierzchołki osiągalne z wierzchołka początkowego.

Wizualizacja:

Złożoność czasowa:

O(V + E), gdzie V — liczba wierzchołków, E — liczba krawędzi.

Każdy węzeł i każda krawędź grafu jest odwiedzana jeden raz.

Złożoność przestrzenna:

O(V), ponieważ używana jest kolejka do przechowywania wierzchołków, a także tablica do przechowywania stanu (odwiedzone wierzchołki).

8.2 Implementacja BFS z użyciem kolejki

Przeszukiwanie wszerz dobrze realizuje się za pomocą struktury danych, jaką jest kolejka.

Implementacja BFS z użyciem kolejki:

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)  # Przetwarzanie węzła
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Przykład użycia:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Dwukierunkowe przeszukiwanie wszerz

BFS jest często używane w grach, kiedy trzeba znaleźć najkrótszą drogę między dwoma punktami w skomplikowanym terenie. Takie zadanie łatwo zamienia się w zadanie znalezienia drogi w grafie między dwoma wierzchołkami. Krawędzie takiego grafu to wszystkie przejezdne ścieżki na mapie.

Jednak aby znaleźć drogę szybciej, często szuka się jej z obu końców. Do tego stosuje się dwukierunkowe BFS.

Zasada działania

Dwukierunkowe przeszukiwanie wszerz (Bidirectional BFS) — to zoptymalizowana wersja algorytmu BFS, który wykonuje dwa równoległe przeszukiwania grafu: jedno od wierzchołka początkowego, a drugie od docelowego. Przeszukiwania trwają, dopóki dwa przeszukiwania się nie spotkają, co znacznie skraca liczbę sprawdzanych wierzchołków i krawędzi w porównaniu z klasycznym BFS.

Kroki algorytmu:

• Inicjalizacja dwóch kolejek: jedna do przeszukiwania od wierzchołka początkowego, druga — od docelowego.
• Inicjalizacja dwóch zbiorów odwiedzonych wierzchołków do śledzenia odwiedzonych wierzchołków w obu kierunkach.
• Wykonywanie naprzemiennego przeszukiwania grafu z dwóch kolejek.
• Przy każdym kroku sprawdza się, czy zbiory odwiedzonych wierzchołków się przecinają. Jeśli znajdzie się przecięcie, ścieżka istnieje.
• Proces trwa, dopóki nie zostanie znaleziony przecięty węzeł lub kolejki się nie opróżnią.

Złożoność czasowa

W najlepszym przypadku: O(2 * (V + E)) = O(V + E), gdzie V — liczba wierzchołków, E — liczba krawędzi.

Dwukierunkowe przeszukiwanie BFS zwykle wykonuje przeszukiwanie mniejszej liczby wierzchołków w porównaniu do jednoprzebiegowego BFS, szczególnie w dużych grafach.

Złożoność przestrzenna:

O(V) dla przechowywania dwóch kolejek i dwóch zbiorów odwiedzonych wierzchołków.

Przykład implementacji dwukierunkowego BFS

Przykład jest bardzo długi — algorytm jest trzy razy dłuższy niż jednokierunkowe przeszukiwanie — więc nie będę go podawać. Kiedy będziecie go naprawdę potrzebować, będziecie w stanie napisać go sami.

8.4 Przykłady zadań rozwiązywanych za pomocą BFS

Klasyczne przykłady zadań rozwiązywanych za pomocą BFS:

1. Znajdowanie najkrótszej drogi w grafie nieskierowanym:

BFS jest używane do znalezienia najkrótszej drogi (minimalnej liczby krawędzi) od wierzchołka początkowego do docelowego w grafie nieskierowanym.

Zastosowanie:

• W systemach nawigacyjnych do znajdowania najkrótszej drogi między punktami.
• W analizie sieci do znajdowania najkrótszej drogi transmisji danych.

2. Sprawdzanie spójności grafu:

Sprawdzanie, czy graf jest spójny, czyli czy istnieje droga między dowolnymi dwoma wierzchołkami.

Zastosowanie:

• W analizie sieci do sprawdzania spójności sieci.
• W analizie sieci społecznościowych do sprawdzania spójności grupy użytkowników.

3. Generowanie labiryntów:

Wykorzystanie BFS do generowania losowych labiryntów z zadanymi właściwościami.

Zastosowanie:

• W aplikacjach gier do tworzenia labiryntów.
• W robotyce do testowania algorytmów nawigacji.

4. Przeszukiwanie wszerz w drzewach:

BFS jest używane do przeszukiwania drzew, aby wykonywać czynności na każdym poziomie drzewa (na przykład wyświetlać wszystkie węzły na każdym poziomie).

Zastosowanie:

• W zadaniach wizualizacji danych, gdzie wymagane jest wyświetlanie danych według poziomów.
• W zadaniach planowania, gdzie wymagane jest wykonywanie działań na każdym poziomie hierarchii.

5. Sprawdzanie dwudzielności grafu:

Sprawdzanie, czy graf jest dwudzielny, czyli czy można jego wierzchołki rozdzielić na dwa zbiory tak, aby krawędzie istniały tylko między wierzchołkami z różnych zbiorów.

Zastosowanie:

• W teorii grafów do sprawdzania dwudzielności grafu.
• W zadaniach kolorowania grafów, gdzie konieczne jest sprawdzenie, czy można pokolorować graf dwoma kolorami.