BFS — Breitensuche einfach erklärt

Die Breitensuche, oder BFS (Breadth-First Search), ist ein Graphalgorithmus, der Knoten in der Reihenfolge ihres Abstands von einem Startknoten besucht. Sie prüft zuerst alle Knoten, die genau eine Kante entfernt sind, dann alle mit zwei Kanten Abstand, dann drei und so weiter.

Diese schichtweise Reihenfolge ist die zentrale Idee. Wenn der Graph ungewichtet ist oder jede Kante die gleichen Kosten hat, liefert BFS außerdem die Länge des kürzesten Pfads vom Startknoten zu jedem erreichbaren Knoten.

Was die Breitensuche macht

BFS verwendet eine Queue, also eine Warteschlange nach dem Prinzip „first in, first out“. Die Queue sorgt dafür, dass die Schichten erhalten bleiben: Früher entdeckte Knoten werden auch früher verarbeitet.

Das übliche Muster ist:

• den Startknoten als besucht markieren
• ihn in die Queue einfügen
• den vordersten Knoten entfernen
• jeden noch nicht besuchten Nachbarn hinten an die Queue anhängen
• wiederholen, bis die Queue leer ist

Wenn du zusätzlich den Vorgänger jedes Knotens speicherst, kannst du nach Abschluss der Suche einen kürzesten Pfad rekonstruieren.

Warum die Queue Schichten erzeugt

Angenommen, Knoten $A$ ist der Start. Seine direkten Nachbarn haben Abstand $1$ von $A$, also kommen sie zuerst in die Queue. Erst nachdem diese Knoten verarbeitet wurden, werden ihre noch nicht besuchten Nachbarn eingefügt, und diese nächste Welle hat dann Abstand $2$.

Deshalb gruppiert BFS Knoten ganz natürlich nach ihrem Abstand vom Start. Sie schätzt nicht, welcher Pfad kurz ist. Die Queue zwingt die Suche dazu, zuerst alle Pfade mit weniger Kanten abzuschließen, bevor längere betrachtet werden.

BFS-Beispiel: Den kürzesten Pfad nach Kantenanzahl finden

Verwende diesen Graphen:

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

Starte bei $A$. Die Queue verändert sich so:

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

Das bedeutet:

Zuerst wird $A$ verarbeitet, dann werden $B$ und $C$ hinzugefügt. Danach werden $B$ und dann $C$ verarbeitet, wodurch $D$ und $E$ hinzukommen. Anschließend werden $D$ und $E$ verarbeitet, und so wird $F$ erreicht.

Die Besuchsreihenfolge von BFS ist also:

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

Die Abstände von $A$ sind:

$$\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$$

Das zeigt den wichtigsten Vorteil. BFS erreicht $F$ mit Abstand $3$, also verwendet der kürzeste Pfad von $A$ nach $F$ genau $3$ Kanten. Ein kürzester Pfad ist $A \to B \to D \to F$. Ein anderer ist $A \to C \to E \to F$.

Häufige Fehler bei BFS

Annehmen, dass BFS immer den billigsten Pfad findet

Das stimmt nur, wenn jede Kante die gleichen Kosten hat oder der Graph als ungewichtet behandelt wird. Wenn Kanten unterschiedliche Gewichte haben, kann BFS einen Pfad mit weniger Kanten, aber höheren Gesamtkosten finden.

Einen Knoten zu spät markieren

Bei der Standard-BFS wird ein Knoten meist schon dann als besucht markiert, wenn er in die Queue eingefügt wird, nicht erst später beim Entfernen. So wird verhindert, dass derselbe Knoten mehrfach in die Queue gelangt.

BFS und DFS verwechseln

BFS durchsucht schichtweise. Die Tiefensuche, also DFS (Depth-First Search), verfolgt erst einen Zweig möglichst tief, bevor sie zurückgeht. Beide eignen sich für unterschiedliche Arten von Fragen.

Vergessen, dass die Reihenfolge von der Nachbarreihenfolge abhängen kann

Die genaue Besuchsreihenfolge innerhalb derselben Schicht kann sich ändern, je nachdem, in welcher Reihenfolge Nachbarn aufgelistet sind. Die Abstandsgarantien bleiben bestehen, aber die Traversierungsreihenfolge kann unterschiedlich sein.

Wann die Breitensuche verwendet wird

BFS ist nützlich, wenn dich Erreichbarkeit, Level-Order-Traversierung in Bäumen oder kürzeste Pfadlängen gemessen an der Anzahl der Kanten interessieren.

Sie kommt auch in Zustandsraumproblemen vor, bei denen jeder Zug die gleichen Kosten hat. Unter dieser Bedingung ist BFS oft der klarste Weg, um die minimale Anzahl von Zügen zu finden.

Eine einfache Merkhilfe für BFS

Stell dir BFS wie eine Welle vor, die sich vom Startknoten nach außen ausbreitet. Jeder Wellenschritt fügt eine weitere Kante an Abstand hinzu.

Wenn du es selbst ausprobieren willst, zeichne einen kleinen Graphen, wähle einen Startknoten und notiere nach jedem Schritt die Queue. Als nächsten Schritt kannst du ein ähnliches Graph-Traversierungsproblem lösen und prüfen, ob die Aussage über den kürzesten Pfad auch dann noch gilt, wenn der Graph gewichtet ist.