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.

Graf z wierzchołkami oznaczonymi literami, pokolorowanymi pierścieniami według odległości od wierzchołka startowego, z kolejką wierzchołków narysowaną poniżej
Graf z wierzchołkami oznaczonymi literami, pokolorowanymi pierścieniami według odległości od wierzchołka startowego, z kolejką wierzchołków narysowaną poniżej

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.

Konrad Zuse (w środku, w okularach) i Heinz Billing (po lewej) na wystawie SYSTEMS ’91 w Monachium. Zuse opisał przeszukiwanie wszerz w 1945, w pracach nad językiem Plankalkül opublikowanych dopiero w 1972.
Konrad Zuse (w środku, w okularach) i Heinz Billing (po lewej) na wystawie SYSTEMS ’91 w Monachium. Zuse opisał przeszukiwanie wszerz w 1945, w pracach nad językiem Plankalkül opublikowanych dopiero w 1972.

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