BFS warstwami — jak patrzę na zadania grafowe.

Widziałem uczniów, którzy uczą się BFS jako algorytmu kolejkowego — dodaj sąsiadów, oznacz jako odwiedzone, powtórz. To nie jest błędne, ale przypomina naukę szachów przez zapamiętanie, jak porusza się każda figura, bez zastanowienia się, dlaczego. Potrafisz to wykonać, ale nie potrafisz się dostosować, gdy plansza wygląda nieznajomo.

Zamiast tego używam takiego ujęcia: BFS to maszyna, która produkuje warstwy. Warstwa 0 to miejsce, w którym zaczynasz. Warstwa k+1 to wszystko, co możesz osiągnąć z warstwy k w jednym kroku, czego wcześniej nie widziałeś. Kolejka to tylko mechanizm; warstwy to idea. Gdy to „kliknie”, około 60% zadań grafowych sprowadza się do wariantów BFS, które faktycznie potrafisz skonstruować.

Co oznacza warstwa k?

Zacznijmy od zwykłego nieważonego najkrótszego ścieżkowania. Masz graf, źródło i chcesz znaleźć minimalną liczbę krawędzi potrzebną, by dotrzeć do każdego wierzchołka. Standardowe wyjaśnienie brzmi: „BFS daje najkrótsze ścieżki, ponieważ eksploruje wierzchołki w kolejności odległości”. To prawda, ale jest to wyjaśnienie bierne — nie mówi ci, jak z tego skorzystać.

Wersja czynna: warstwa k zawiera dokładnie te wierzchołki, do których da się dotrzeć ze źródła w k krokach i nie mniej. Gdy zdejmujesz wierzchołek z kolejki, jego odległość jest już ostateczna. Każdy jeszcze nieodwiedzony sąsiad należy do warstwy k+1. Nie tylko wyznaczasz odległości — dzielisz graf na koncentryczne powłoki.

To ma znaczenie, ponieważ w momencie, gdy opiszesz zadanie jako „jaka jest minimalna liczba kroków, by przejść ze stanu A do stanu B?”, odpowiedzią jest BFS, a struktura warstw mówi ci, że odpowiedzią jest numer warstwy, w której B pojawia się po raz pierwszy.

BFS z wieloma źródłami

Załóżmy teraz, że nie masz jednego źródła — masz ich wiele. Ogień rozprzestrzeniający się po siatce, gnijące pomarańcze, strażnicy w labiryncie roztaczający swój wpływ. Chcesz znaleźć minimalną odległość od dowolnego źródła do każdej komórki.

Uczniowie często próbują uruchomić BFS osobno z każdego źródła i wziąć minimum. To działa, ale ma złożoność O(źródła × V), podczas gdy mogłoby to być O(V + E). Rozwiązanie jest eleganckie: zainicjuj kolejkę wszystkimi źródłami jednocześnie, z odległością 0. Warstwa 0 to teraz cały zbiór źródeł. Warstwa 1 to wszystko, co sąsiaduje z dowolnym źródłem. BFS przebiega identycznie.

// Multi-source BFS — all sources start at distance 0
queue<pair<int,int>> q;
vector<vector<int>> dist(rows, vector<int>(cols, -1));

for (auto [r, c] : sources) {
    dist[r][c] = 0;
    q.push({r, c});
}

while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (auto [dr, dc] : directions) {
        int nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (dist[nr][nc] != -1) continue;
        dist[nr][nc] = dist[r][c] + 1;
        q.push({nr, nc});
    }
}

Kluczowa obserwacja: nie wykonujesz wielu przebiegów BFS. Wykonujesz jeden BFS, w którym warstwa 0 po prostu zawiera wiele wierzchołków. Abstrakcja się utrzymuje — warstwa k nadal oznacza „minimalną odległość k od dowolnego źródła”. Kod jest identyczny jak w BFS z jednym źródłem; zmienia się tylko inicjalizacja.

Moi uczniowie rzadko spotykają się z tą techniką pod jej podręcznikową nazwą. W mojej grupie funkcjonuje ona jako Pizza-BFS — nazwana tak od jednego z moich autorskich zadań — i gdy raz je rozwiążesz, zainicjowanie kolejki wszystkimi źródłami na odległości 0 przestaje być sztuczką, a staje się odruchem.

Adam spędził kiedyś dużo czasu nad zadaniem z siatką, w którym infekcja zombie rozprzestrzeniała się z kilku początkowych komórek. Napisał pętlę po zainfekowanych komórkach i uruchamiał BFS z każdej z nich. Odpowiedź była poprawna, ale przekroczył limit czasu. Przepisaliśmy inicjalizację w pięć minut.

0-1 BFS i kiedy warstwy się rozpadają

Standardowy BFS zakłada, że każda krawędź ma taką samą wagę — właśnie dzięki temu struktura warstw działa. Jeśli dodasz krawędzie o wadze 0 i wadze 1, warstwy zaczynają się rozjeżdżać: przejście krawędzią o koszcie 0 nie powinno zwiększać numeru warstwy.

0-1 BFS radzi sobie z tym za pomocą kolejki dwustronnej (deque) zamiast zwykłej kolejki. Krawędzie o koszcie zero trafiają na początek (ta sama warstwa); krawędzie o koszcie jeden trafiają na koniec (następna warstwa). Struktura warstw zostaje zachowana — po prostu uważniej pilnujesz, które przejścia zwiększają licznik warstwy.

Wspominam o tym nie po to, by w pełni nauczyć 0-1 BFS, ale by pokazać, że ujęcie warstwowe pozwala przewidzieć, kiedy standardowy BFS wymaga modyfikacji. Jeśli koszty krawędzi łamią założenie „każdy krok kosztuje 1”, musisz zmodyfikować mechanizm. Dijkstra to przypadek ogólny; 0-1 BFS to jego efektywny przypadek szczególny. Intuicja warstwowa mówi ci, dlaczego oba istnieją.

BFS na niejawnych grafach stanów

Tu to ujęcie naprawdę pokazuje swoją wartość. Wiele zadań olimpijskich w ogóle nie jest sformułowanych jako zadania grafowe — to łamigłówki, symulacje, przeszukiwania kombinatoryczne. Ale mają one niejawną strukturę grafu: stany są wierzchołkami, dozwolone ruchy są krawędziami, a ty szukasz minimalnej liczby ruchów.

Ruchy skoczkiem na szachownicy. Piętnastki (sliding puzzle). Przełączanie przełączników, gdzie każdy wpływa na sąsiadów. Drabinki słowne. Graf nigdy nie jest narysowany — generujesz go w locie podczas BFS.

Pytanie, które zawsze trzeba sobie zadać, brzmi: czym jest jeden stan? Dla ruchów skoczkiem to pozycja na szachownicy. Dla łamigłówki z przełącznikami to aktualna konfiguracja wszystkich przełączników. Dla piętnastki to cały układ planszy (uważaj z N — przestrzeń stanów szybko eksploduje).

Gdy potrafisz opisać, co oznacza jedna warstwa BFS w języku twojego zadania — „wszystkie konfiguracje planszy osiągalne w dokładnie k ruchach”, „wszystkie konfiguracje przełączników osiągalne przy k przełączeniach” — kod pisze się sam. Nie robisz wtedy BFS na grafie. Robisz BFS na przestrzeni stanów, a to ten sam algorytm.

Tomek utknął na zadaniu, w którym przełączasz bit w ciągu binarnym, a wszystkie sąsiednie bity też się przełączają, i chcesz osiągnąć stan docelowy za pomocą minimalnej liczby przełączeń. Cały czas próbował znaleźć wzorzec zachłanny. Zapytałem go: „czym jest stan?”. Odpowiedział: „aktualnym ciągiem”. Zapytałem: „czym jest przejście?”. Odpowiedział: „przełączeniem pozycji i, co zmienia bity i-1, i, i+1”. Wtedy zamilkł na chwilę i napisał BFS. Jedenaście minut później miał AC.

Lista kontrolna warstw

Gdy napotykam zadanie i zastanawiam się, czy pasuje do niego BFS, przechodzę przez taką listę:

1. Czym jest stan? Czy mogę go zapisać wystarczająco kompaktowo, by umieścić go w kolejce i użyć jako klucza w mapie?
2. Czym jest przejście? Mając dany stan, jakie stany mogę osiągnąć w jednym „kroku”?
3. Co oznacza jedna warstwa? „Wszystkie stany osiągalne w dokładnie k krokach” — czy to zdanie ma sens dla mojego zadania?
4. Czy mam wiele stanów początkowych? Jeśli tak, zainicjuj kolejkę wszystkimi z nich na odległości 0.
5. Czy wszystkie przejścia mają jednakowy koszt? Jeśli nie, rozważ 0-1 BFS lub algorytm Dijkstry.

Jeśli potrafię jasno odpowiedzieć na pytania 1-3, piszę BFS. Reszta to już mechanika.

Uczę BFS przez pryzmat warstw, a nie jako algorytmu kolejkowego, ponieważ kolejka to tylko szczegół implementacyjny. Uczniowie, którzy rozumieją warstwy, potrafią odtworzyć BFS od zera, nawet jeśli zapomną dokładnego kodu. Uczniowie, którzy zapamiętali wzorzec kolejkowy, utykają, gdy zadanie nie wygląda jak szablon.

W kontekście przygotowań do OI: zadania wykorzystujące BFS na niejawnych grafach stanów regularnie pojawiają się w pierwszych dwóch etapach — są wystarczająco trudne, by odsiać uczniów, którzy potrafią rozwiązywać tylko podręcznikowe grafy, ale są całkowicie osiągalne, jeśli zinternalizowałeś model warstwowy. Oswój się z pytaniem „czym jest jeden stan w tym zadaniu?”, a przekonasz się, że zadania grafowe przestają być odrębną kategorią.