Przeszukiwanie wszerz

Przeszukiwanie wszerz

Przeszukiwanie wszerz (BFS) to podstawowy algorytm przeszukiwania grafu. Rozpoczyna się od wybranego wierzchołka s i ma na celu odwiedzenie wszystkich osiągalnych wierzchołków. Wynikiem działania algorytmu jest drzewo przeszukiwania, które zawiera najkrótsze ścieżki z s do wszystkich osiągalnych wierzchołków. Algorytm działa zarówno w grafach skierowanych, jak i nieskierowanych.

Algorytm

Algorytm BFS przedstawia się następująco:

funkcja BreadthFirstSearch (Graf G, Wierzchołek s)
     dla każdego wierzchołka u z G:
         kolor[u] = biały
         odleglosc[u] = inf
         rodzic[u] = NIL
     kolor[s] = SZARY
     odleglosc[s] = 0
     rodzic[s] = NIL
     Q.push(s)
     dopóki kolejka Q nie jest pusta:
         u = Q.front()
         Q.pop()
         dla każdego v z listy sąsiedztwa u:
             jeżeli v jest biały:
                 kolor[v] = SZARY
                 odleglosc[v] = odleglosc[u] + 1
                 rodzic[v] = u
                 Q.push(v)
         kolor[u] = CZARNY

Na początku wszystkie wierzchołki są oznaczone jako białe (nieodwiedzone), a ich odległości ustawione na nieskończoność. Wierzchołek s jest oznaczany na szaro (odwiedzony), a jego odległość na 0. Następnie, węzeł s jest dodawany do kolejki. Algorytm przetwarza kolejkę, odwiedzając sąsiadów i aktualizując ich kolory oraz pola odległości i rodzica.

Właściwości

• Złożoność pamięciowa: O(|V| + |E|) dla listy sąsiedztwa, O(|V|²) dla macierzy sąsiedztwa.
• Złożoność czasowa: O(|V| + |E|), ponieważ algorytm przetwarza wszystkie krawędzie i węzły.
• Kompletność: Algorytm jest kompletny; znajdzie rozwiązanie, jeśli istnieje.

Zastosowania

BFS znajduje zastosowanie w wielu problemach teorii grafów, w tym:

• Odnalezienie wszystkich połączonych węzłów w grafie.
• Odnalezienie najkrótszej ścieżki między dwoma wierzchołkami (bez uwzględniania wag krawędzi).
• Sprawdzanie, czy graf jest dwudzielny.