Przeszukiwanie wszerz (BFS)
Wrzuć kamień do stawu, a fale rozejdą się równo pierścieniami. Przeszukiwanie wszerz bada graf w ten sam sposób: najpierw wszystko o jeden krok od startu, potem wszystko o dwa kroki i tak dalej. To ta prosta kolejność sprawia, że znajduje ono najkrótsze ścieżki.
Idea
Graf to zbiór wierzchołków połączonych krawędziami: miejsca i drogi, ludzie i przyjaźnie, pola labiryntu i przejścia między nimi. Przeszukiwanie wszerz odpowiada na pytanie: dokąd mogę dotrzeć stąd i w ilu najmniej krokach? Przechowuje kolejkę wierzchołków do odwiedzenia. Branie wierzchołków z początku i dodawanie nowych na koniec sprawia, że wierzchołki są obsługiwane w kolejności odkrycia.
Krok po kroku
Wstaw start do kolejki z odległością 0. Weź wierzchołek z początku. Dla każdego sąsiada, którego jeszcze nie widziano, zapisz odległość o jeden większą niż odległość bieżącego wierzchołka, zapamiętaj bieżący wierzchołek jako drogę, którą do niego dotarto, i dodaj go na koniec kolejki. Pomijaj sąsiadów widzianych wcześniej. Powtarzaj, aż kolejka będzie pusta albo cel zostanie osiągnięty.
Przykład
Weźmy graf z krawędziami A–B, A–C, B–D, C–D, C–E i D–F i zacznijmy od wierzchołka A. Wzięcie A z kolejki znajduje B i C w odległości 1. Wzięcie B znajduje D w odległości 2. Wzięcie C pokazuje, że wierzchołek D był już widziany, i znajduje E w odległości 2. Wzięcie D znajduje F w odległości 3. E i F nie znajdują nic nowego i kolejka jest pusta. Cofając się po zapamiętanych wierzchołkach od F, dostajemy F ← D ← B ← A, więc najkrótsza ścieżka z A do F to A → B → D → F, długości trzech krawędzi.
Dlaczego odległości są poprawne
Każdy wierzchołek w odległości 1 trafia do kolejki przed jakimkolwiek wierzchołkiem w odległości 2, każdy w odległości 2 przed jakimkolwiek w odległości 3 i tak dalej, bo sąsiedzi wierzchołka trafiają do kolejki dopiero wtedy, gdy on sam z niej wychodzi. Pierwsza ścieżka, która dociera do wierzchołka, ma więc najmniej krawędzi, a BFS nigdy nie musi poprawiać odległości. Każdy wierzchołek jest brany raz, a każda krawędź sprawdzana z obu końców, więc praca rośnie wraz z liczbą wierzchołków i krawędzi.
Historia i zastosowania
Konrad Zuse opisał przeszukiwanie wszerz w 1945 roku w pracy nad swoim językiem Plankalkül, opublikowanej dopiero w 1972 roku. Edward F. Moore wymyślił je na nowo w 1959 roku, by znaleźć najkrótszą drogę wyjścia z labiryntu, a C. Y. Lee użył go w 1961 roku do prowadzenia połączeń na płytkach drukowanych. Dziś znajduje najmniejszą liczbę ruchów w łamigłówkach, stopnie oddalenia w sieciach społecznościowych, strony, do których robot internetowy dociera najpierw, i najbliższe wolne pole w grach. Gdy krawędzie mają długości, jego uogólnieniem jest algorytm Dijkstry.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Odwiedzany wierzchołek jest wyróżniony, wierzchołki czekające w kolejce są niebieskie, a odwiedzone – zielone, każdy ze swoją odległością. Kolejka jest pokazana pod grafem, od początku. Przełącz kliknięcie na Cel i wybierz wierzchołek, aby się na nim zatrzymać i zobaczyć najkrótszą ścieżkę, albo utwórz nowy graf z większą liczbą wierzchołków i krawędzi.
Często zadawane pytania
Jaka jest złożoność czasowa BFS?
O(V + E) dla V wierzchołków (vertices) i E krawędzi (edges): każdy wierzchołek raz wchodzi do kolejki i raz z niej wychodzi, a każda krawędź jest sprawdzana z obu końców. Potrzeba O(V) dodatkowej pamięci na kolejkę i odległości.
Dlaczego BFS używa kolejki?
Bo zasada „pierwszy wchodzi, pierwszy wychodzi” utrzymuje wierzchołki w kolejności odkrycia, czyli w kolejności ich odległości. Ze stosem zamiast kolejki przeszukiwanie najpierw schodziłoby w głąb: to przeszukiwanie w głąb.
Czy BFS znajduje najkrótsze ścieżki w grafach ważonych?
Na ogół nie: liczy krawędzie, a nie ich długości. Dla grafów ważonych bez ujemnych krawędzi użyj algorytmu Dijkstry. Jeśli każda waga to 0 lub 1, działa wariant zwany 0-1 BFS.
Gdzie stosuje się BFS?
Do rozwiązywania łamigłówek i labiryntów w najmniejszej liczbie ruchów, szukania znajomych znajomych w sieciach społecznościowych, przeszukiwania sieci WWW poziom po poziomie, rozgłaszania w sieciach oraz jako element innych algorytmów, na przykład do wyznaczania maksymalnego przepływu.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj przeszukiwanie wszerz