Przeszukiwanie wszerz (BFS)
Przegląda graf warstwa po warstwie. O tym, który wierzchołek jest następny, decyduje kolejka, więc najbliższe wierzchołki zawsze są odwiedzane jako pierwsze.
- czas O(V + E)
- pamięć O(V)
- używa kolejki
Co to znaczy?
- Wierzchołek: punkt grafu, tu narysowany jako kółko z literą.
- Krawędź: linia łącząca dwa wierzchołki. Tutaj można nią przejść w obie strony.
- Sąsiedzi: wierzchołki połączone z danym wierzchołkiem krawędzią. Są sprawdzani w kolejności alfabetycznej.
- Kolejka: kto pierwszy wszedł, ten pierwszy wychodzi. BFS zawsze bierze wierzchołek, który czeka najdłużej.
- Stos: kto ostatni wszedł, ten pierwszy wychodzi. DFS zawsze idzie dalej od wierzchołka, do którego dotarł ostatnio.
- V i E: liczba wierzchołków i krawędzi. O(V + E) oznacza, że każdy wierzchołek i każda krawędź są obsługiwane stałą liczbę razy.
- w kolejce
- bieżący
- gotowy
- krawędź drzewa przeszukiwania
- pominięta krawędź
Zacznij od wierzchołka A. Naciśnij Odtwórz albo przechodź przez przeszukiwanie krok po kroku.
Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.
Spróbuj: Wybierz graf z dwiema częściami. Do wierzchołków niepołączonych ze startem przeszukiwanie nigdy nie dociera.
Jak to działa
BFS wstawia wierzchołek startowy do kolejki. Potem raz za razem wyjmuje wierzchołek z początku kolejki i dodaje jego nowych sąsiadów na koniec. Kolejka obsługuje wierzchołki w kolejności przybycia, więc każdy wierzchołek odległy o jedną krawędź jest gotowy, zanim przyjdzie kolej na którykolwiek odległy o dwie. Liczba przy wierzchołku to jego odległość od startu, czyli najmniejsza liczba krawędzi, po których można do niego dojść.
Kiedy warto go użyć
BFS przydaje się, gdy potrzebna jest najkrótsza droga liczona w krokach: najmniej ruchów w łamigłówce, najmniej przeskoków w sieci, znajomi i znajomi znajomych. W dużym grafie kolejka potrafi mocno urosnąć, bo mieści naraz całą warstwę.