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|2) 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.
