BFS — wyjaśnienie algorytmu przeszukiwania wszerz

Przeszukiwanie wszerz, czyli BFS, to algorytm grafowy, który odwiedza wierzchołki w kolejności ich odległości od wierzchołka startowego. Najpierw sprawdza każdy wierzchołek oddalony o jedną krawędź, potem te oddalone o dwie krawędzie, następnie o trzy i tak dalej.

Ten porządek warstwa po warstwie jest kluczową ideą. Jeśli graf jest nieważony albo każda krawędź ma ten sam koszt, BFS wyznacza też długość najkrótszej ścieżki od wierzchołka startowego do każdego osiągalnego wierzchołka.

Co robi przeszukiwanie wszerz

BFS używa kolejki, czyli struktury typu first-in, first-out. To właśnie kolejka zachowuje porządek warstw: wierzchołki odkryte wcześniej są przetwarzane wcześniej.

Typowy schemat wygląda tak:

• oznacz wierzchołek startowy jako odwiedzony
• wstaw go do kolejki
• usuń wierzchołek z początku kolejki
• dodaj każdego nieodwiedzonego sąsiada na koniec kolejki
• powtarzaj, aż kolejka będzie pusta

Jeśli dodatkowo zapisujesz rodzica każdego wierzchołka, po zakończeniu przeszukiwania możesz odtworzyć jedną z najkrótszych ścieżek.

Dlaczego kolejka tworzy warstwy

Załóżmy, że wierzchołek $A$ jest początkiem. Jego bezpośredni sąsiedzi są w odległości $1$ od $A$, więc trafiają do kolejki jako pierwsi. Dopiero po przetworzeniu tych wierzchołków do kolejki trafiają ich nieodwiedzeni sąsiedzi, co oznacza, że następna fala ma odległość $2$.

Dlatego BFS w naturalny sposób grupuje wierzchołki według odległości od startu. Nie próbuje oszacować, która ścieżka jest krótka. Kolejka wymusza zakończenie wszystkich ścieżek z mniejszą liczbą krawędzi, zanim algorytm rozważy dłuższe.

Przykład BFS: znajdowanie najkrótszej ścieżki według liczby krawędzi

Użyj tego grafu:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Zacznij od $A$. Kolejka zmienia się tak:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Oto co to oznacza:

Najpierw przetwarzamy $A$, a potem dodajemy $B$ i $C$. Następnie przetwarzamy $B$, a potem $C$, co dodaje $D$ i $E$. Po tym przetwarzamy $D$ i $E$, co prowadzi do $F$.

Zatem kolejność odwiedzania w BFS to:

$$A,\ B,\ C,\ D,\ E,\ F$$

Odległości od $A$ wynoszą:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

To pokazuje główną korzyść. BFS dociera do $F$ w odległości $3$, więc najkrótsza ścieżka z $A$ do $F$ używa $3$ krawędzi. Jedna z najkrótszych ścieżek to $A \to B \to D \to F$. Inna to $A \to C \to E \to F$.

Typowe błędy w BFS

Założenie, że BFS zawsze znajduje najtańszą ścieżkę

To jest prawdą tylko wtedy, gdy każda krawędź ma ten sam koszt albo gdy graf traktujemy jako nieważony. Jeśli krawędzie mają różne wagi, BFS może znaleźć ścieżkę z mniejszą liczbą krawędzi, ale o większym łącznym koszcie.

Zbyt późne oznaczanie wierzchołka

W standardowym BFS wierzchołek zwykle oznacza się jako odwiedzony w chwili dodania do kolejki, a nie dopiero wtedy, gdy zostanie z niej usunięty. To zapobiega wielokrotnemu dodawaniu tego samego wierzchołka do kolejki.

Mylenie BFS i DFS

BFS przeszukuje warstwami. Przeszukiwanie w głąb, czyli DFS, podąża jedną gałęzią tak daleko, jak się da, zanim zacznie się cofać. Te algorytmy dobrze odpowiadają na różne typy pytań.

Zapominanie, że kolejność może zależeć od kolejności sąsiadów

Dokładna kolejność odwiedzania w obrębie tej samej warstwy może się zmieniać w zależności od tego, jak wypisani są sąsiedzi. Gwarancje dotyczące odległości nadal obowiązują, ale sama kolejność przejścia może być inna.

Kiedy używa się przeszukiwania wszerz

BFS jest przydatny, gdy interesuje Cię osiągalność, przechodzenie drzewa poziomami albo długości najkrótszych ścieżek mierzone liczbą krawędzi.

Pojawia się też w problemach przestrzeni stanów, w których każdy ruch ma ten sam koszt. W takim przypadku BFS jest często najprostszym sposobem na znalezienie minimalnej liczby ruchów.

Prosty sposób, by zapamiętać BFS

Pomyśl o BFS jak o fali rozchodzącej się na zewnątrz od wierzchołka startowego. Każdy kolejny krok fali dodaje jeszcze jedną krawędź odległości.

Aby wypróbować własną wersję, narysuj mały graf, wybierz wierzchołek startowy i zapisuj stan kolejki po każdym kroku. Jeśli chcesz pójść dalej, rozwiąż podobne zadanie z przechodzeniem grafu i sprawdź, czy twierdzenie o najkrótszej ścieżce nadal działa, gdy graf jest ważony.