BFS in Schichten — wie ich Graphaufgaben sehe.

Ich habe schon Schüler erlebt, die BFS als reinen Warteschlangen-Algorithmus lernen — Nachbarn einreihen, als besucht markieren, wiederholen. Das ist nicht falsch, aber es ist wie Schach zu lernen, indem man auswendig lernt, wie sich jede Figur bewegt, ohne über das Warum nachzudenken. Du kannst es ausführen, aber du kannst dich nicht anpassen, wenn das Brett unbekannt aussieht.

Der Rahmen, den ich stattdessen benutze: BFS ist eine Maschine, die Schichten erzeugt. Schicht 0 ist dort, wo du startest. Schicht k+1 ist alles, was du von Schicht k aus in einem Schritt erreichen kannst und noch nicht gesehen hast. Die Warteschlange ist nur der Mechanismus; die Schichten sind die Idee. Sobald das klickt, lösen sich etwa 60 % der Graphaufgaben in BFS-Varianten auf, die du tatsächlich konstruieren kannst.

Was bedeutet Schicht k?

Zuerst der einfache, ungewichtete kürzeste Weg. Du hast einen Graphen, eine Quelle, und du willst die minimale Anzahl an Kanten, um jeden Knoten zu erreichen. Die Standarderklärung lautet: „BFS liefert kürzeste Wege, weil es Knoten in Reihenfolge ihrer Distanz erkundet.“ Das stimmt, ist aber passiv — es sagt dir nicht, wie du es benutzt.

Aktive Version: Schicht k enthält genau die Knoten, die von der Quelle aus in k Schritten und nicht weniger erreichbar sind. Wenn du einen Knoten aus der Warteschlange entnimmst, ist seine Distanz endgültig festgelegt. Jeder Nachbar, den du noch nicht besucht hast, gehört zu Schicht k+1. Du findest nicht nur Distanzen — du unterteilst den Graphen in konzentrische Schalen.

Das ist wichtig, denn sobald du eine Aufgabe als „Was ist die minimale Anzahl an Schritten, um von Zustand A zu Zustand B zu gelangen?“ beschreibst, ist BFS deine Antwort, und die Schichtstruktur sagt dir, dass die Antwort die Schichtnummer ist, in der B zum ersten Mal auftaucht.

Multi-Source-BFS

Nimm nun an, du hast nicht eine Quelle — du hast viele. Feuer, das sich durch ein Gitter ausbreitet, Orangen, die faulen, Wächter in einem Labyrinth, die ihren Einflussbereich ausstrahlen. Du willst die minimale Distanz von irgendeiner Quelle zu jeder Zelle.

Schüler versuchen oft, BFS von jeder Quelle einzeln laufen zu lassen und dann das Minimum zu nehmen. Das funktioniert, ist aber O(Quellen × V), obwohl es O(V + E) sein könnte. Die Lösung ist elegant: Du befüllst die Warteschlange gleichzeitig mit allen Quellen auf Distanz 0. Schicht 0 ist jetzt die gesamte Menge der Quellen. Schicht 1 ist alles, was an irgendeine Quelle angrenzt. Der BFS-Ablauf bleibt identisch.

// 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});
    }
}

Die zentrale Erkenntnis: Du machst nicht mehrere BFS-Durchläufe. Du machst einen einzigen BFS, bei dem Schicht 0 zufällig mehrere Knoten enthält. Die Abstraktion bleibt gültig — Schicht k bedeutet immer noch „minimale Distanz k von irgendeiner Quelle“. Der Code ist identisch zum Single-Source-BFS; nur die Initialisierung ändert sich.

Meine Schüler begegnen dieser Technik selten unter ihrem Lehrbuchnamen. In meiner Gruppe heißt sie Pizza-BFS — benannt nach einer meiner Signature-Aufgaben — und sobald du diese einmal gelöst hast, hört das Befüllen der Warteschlange mit jeder Quelle auf Distanz 0 auf, ein Trick zu sein, und wird zum Reflex.

Adam hat einmal lange an einer Gitteraufgabe gesessen, bei der sich eine Zombie-Infektion von mehreren Startzellen aus ausbreitete. Er schrieb eine Schleife über die infizierten Zellen und ließ BFS von jeder einzelnen laufen. Richtige Antwort, aber Zeitlimit überschritten. Wir haben die Initialisierung in fünf Minuten umgeschrieben.

0-1-BFS und wann Schichten zusammenbrechen

Standard-BFS geht davon aus, dass jede Kante das gleiche Gewicht hat — genau das lässt die Schichtstruktur funktionieren. Wenn du Kanten mit Gewicht 0 und Gewicht 1 hinzufügst, beginnt die Schichtstruktur auszufransen: Die Bewegung entlang einer Kante mit Kosten 0 sollte deine Schichtnummer nicht erhöhen.

0-1-BFS löst das mit einer Deque statt einer Warteschlange. Kanten mit Kosten 0 werden vorne eingefügt (gleiche Schicht); Kanten mit Kosten 1 werden hinten angehängt (nächste Schicht). Die Schichtstruktur bleibt erhalten — du achtest nur genauer darauf, welche Übergänge den Schichtzähler erhöhen.

Ich erwähne das hier nicht, um 0-1-BFS vollständig zu erklären, sondern um zu zeigen, dass das Schichtmodell vorhersagt, wann Standard-BFS angepasst werden muss. Wenn deine Kantenkosten die Annahme „jeder Schritt kostet 1“ verletzen, musst du den Mechanismus ändern. Dijkstra ist der allgemeine Fall; 0-1-BFS ist der effiziente Spezialfall. Die Schicht-Intuition sagt dir, warum es beide gibt.

BFS auf impliziten Zustandsgraphen

Genau hier zahlt sich das Modell wirklich aus. Viele Olympiade-Aufgaben sind gar nicht als Graphaufgaben formuliert — es sind Rätsel, Simulationen, kombinatorische Suchen. Aber sie haben eine implizite Graphstruktur: Zustände sind Knoten, gültige Züge sind Kanten, und du willst die minimale Anzahl an Zügen.

Springerzüge auf einem Schachbrett. Schiebepuzzles. Schalter umlegen, wobei jeder Schalter seine Nachbarn beeinflusst. Word Ladders. Der Graph wird nie gezeichnet — du erzeugst ihn während des BFS zur Laufzeit.

Die Frage, die du dir immer stellen solltest, lautet: Was ist ein Zustand? Bei Springerzügen ist es eine Brettposition. Bei einem Schalter-Puzzle ist es die aktuelle Konfiguration aller Schalter. Bei einem Schiebepuzzle ist es das gesamte Brett-Layout (Vorsicht bei N — der Zustandsraum explodiert schnell).

Wenn du beschreiben kannst, was eine BFS-Schicht in der Sprache deiner Aufgabe bedeutet — „alle Brettkonfigurationen, die in genau k Zügen erreichbar sind“, „alle Schalterkonfigurationen, die mit k Umlegungen erreichbar sind“ —, schreibt sich der Code von selbst. Du machst kein Graph-BFS. Du machst Zustandsraum-BFS, und es ist derselbe Algorithmus.

Tomek hing an einer Aufgabe fest, bei der man ein Bit in einem Binärstring umlegt und alle benachbarten Bits ebenfalls kippen, und man will die minimale Anzahl an Umlegungen, um ein Ziel zu erreichen. Er versuchte immer wieder, ein gieriges Muster zu finden. Ich fragte ihn: „Was ist ein Zustand?“ Er sagte: „Der aktuelle String.“ Ich fragte: „Was ist ein Übergang?“ Er sagte: „Position i umlegen, was die Bits i-1, i, i+1 verändert.“ Dann hielt er inne und schrieb BFS. Elf Minuten später hatte er AC.

Die Schicht-Checkliste

Wenn ich auf eine Aufgabe stoße und entscheiden muss, ob BFS anwendbar ist, gehe ich diese Liste durch:

1. Was ist ein Zustand? Kann ich ihn kompakt genug darstellen, um ihn in eine Warteschlange zu legen und als Map-Schlüssel zu verwenden?
2. Was ist ein Übergang? Welche Zustände kann ich von einem gegebenen Zustand aus in einem „Schritt“ erreichen?
3. Was bedeutet eine Schicht? „Alle Zustände, die in genau k Schritten erreichbar sind“ — ergibt dieser Satz für meine Aufgabe Sinn?
4. Habe ich mehrere Startzustände? Falls ja, befülle die Warteschlange mit allen gleichzeitig auf Distanz 0.
5. Haben alle Übergänge die gleichen Kosten? Falls nein, ziehe 0-1-BFS oder Dijkstra in Betracht.

Wenn ich die Fragen 1-3 sauber beantworten kann, schreibe ich BFS. Der Rest ist Mechanik.

Der Grund, warum ich BFS als Schichten unterrichte statt als Warteschlangen-Algorithmus, ist, dass die Warteschlange ein Implementierungsdetail ist. Schüler, die Schichten verstehen, können BFS von Grund auf neu konstruieren, wenn sie den genauen Code vergessen haben. Schüler, die nur das Warteschlangenmuster auswendig gelernt haben, stecken fest, sobald die Aufgabe nicht wie die Vorlage aussieht.

Speziell für die OI-Vorbereitung: Aufgaben, die BFS auf impliziten Zustandsgraphen verwenden, tauchen regelmäßig in den ersten beiden Runden auf — sie sind schwer genug, um Schüler herauszufiltern, die nur Lehrbuchgraphen lösen können, aber sie sind vollkommen zu bewältigen, wenn du das Schichtmodell verinnerlicht hast. Gewöhne dich an die Frage „Was ist ein Zustand in dieser Aufgabe?“, und du wirst merken, dass Graphaufgaben aufhören, sich wie eine eigene Kategorie anzufühlen.