Breitensuche (BFS)

Werfen Sie einen Stein in einen Teich, und die Wellen breiten sich gleichmäßig in Ringen aus. Die Breitensuche erkundet einen Graphen genauso: zuerst alles, was einen Schritt vom Start entfernt ist, dann alles, was zwei Schritte entfernt ist, und so weiter. Genau diese einfache Reihenfolge lässt sie kürzeste Wege finden.

Ein Graph aus Knoten mit Buchstaben, in Ringen nach ihrem Abstand vom Startknoten eingefärbt, darunter eine Warteschlange aus Knoten
Ein Graph aus Knoten mit Buchstaben, in Ringen nach ihrem Abstand vom Startknoten eingefärbt, darunter eine Warteschlange aus Knoten

Die Idee

Ein Graph ist eine Menge von Knoten, die durch Kanten verbunden sind: Orte und Straßen, Menschen und Freundschaften, Felder eines Labyrinths und die Durchgänge dazwischen. Die Breitensuche beantwortet die Frage: Was kann ich von hier aus erreichen, und in wie wenigen Schritten? Sie führt eine Warteschlange der Knoten, die noch zu besuchen sind. Weil Knoten vorne entnommen und neue hinten angefügt werden, werden die Knoten in der Reihenfolge bearbeitet, in der sie entdeckt wurden.

Schritt für Schritt

Legen Sie den Start mit Abstand 0 in die Warteschlange. Nehmen Sie den Knoten vorne. Notieren Sie für jeden Nachbarn, der noch nicht gesehen wurde, als Abstand eins mehr als beim aktuellen Knoten, merken Sie sich den aktuellen Knoten als den, über den er erreicht wurde, und fügen Sie ihn hinten an die Warteschlange an. Überspringen Sie Nachbarn, die schon gesehen wurden. Wiederholen Sie das, bis die Warteschlange leer ist oder das Ziel erreicht ist.

Ein Beispiel

Nehmen Sie einen Graphen mit den Kanten A–B, A–C, B–D, C–D, C–E und D–F, und starten Sie bei A. Wird A aus der Warteschlange genommen, findet die Suche B und C mit Abstand 1. Bei B findet sie D mit Abstand 2. Bei C stellt sie fest, dass D schon gesehen wurde, und findet E mit Abstand 2. Bei D findet sie F mit Abstand 3. E und F bringen nichts Neues, und die Warteschlange ist leer. Folgt man den gemerkten Knoten von F zurück, ergibt sich F ← D ← B ← A. Ein kürzester Weg von A nach F ist also A → B → D → F, drei Kanten lang.

Warum die Abstände stimmen

Jeder Knoten mit Abstand 1 kommt vor jedem Knoten mit Abstand 2 in die Warteschlange, jeder Knoten mit Abstand 2 vor jedem mit Abstand 3 und so weiter, denn die Nachbarn eines Knotens kommen erst in die Warteschlange, wenn der Knoten selbst herausgenommen wird. Der erste Weg, der einen Knoten erreicht, hat also die wenigsten Kanten, und BFS muss nie einen Abstand korrigieren. Jeder Knoten wird einmal genommen und jede Kante von beiden Enden aus betrachtet, also wächst der Aufwand mit der Zahl der Knoten plus der Zahl der Kanten.

Geschichte und Anwendungen

Konrad Zuse beschrieb die Breitensuche 1945 in Arbeiten zu seiner Sprache Plankalkül, die erst 1972 veröffentlicht wurden. Edward F. Moore erfand sie 1959 neu, um den kürzesten Weg aus einem Labyrinth zu finden, und C. Y. Lee nutzte sie 1961, um Leiterbahnen auf Platinen zu verlegen. Heute findet sie die wenigsten Züge in Rätseln, die Grade der Trennung in sozialen Netzwerken, die Seiten, die ein Webcrawler zuerst erreicht, und das nächste freie Feld in Spielen. Haben Kanten Längen, verallgemeinert sie der Dijkstra-Algorithmus.

Konrad Zuse (Mitte, mit Brille) und Heinz Billing (links) auf der Messe SYSTEMS ’91 in München. Zuse beschrieb die Breitensuche 1945 in Arbeiten zu seiner Sprache Plankalkül, die erst 1972 veröffentlicht wurden.
Konrad Zuse (Mitte, mit Brille) und Heinz Billing (links) auf der Messe SYSTEMS ’91 in München. Zuse beschrieb die Breitensuche 1945 in Arbeiten zu seiner Sprache Plankalkül, die erst 1972 veröffentlicht wurden.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Der gerade besuchte Knoten ist hervorgehoben, Knoten in der Warteschlange sind blau und besuchte Knoten grün, jeweils mit ihrem Abstand. Die Warteschlange wird unter dem Graphen angezeigt, vorne zuerst. Stellen Sie den Klick auf Ziel um und wählen Sie einen Knoten, um dort anzuhalten und den kürzesten Weg zu sehen, oder erzeugen Sie einen neuen Graphen mit mehr Knoten und Kanten.

Häufig gestellte Fragen

Welche Zeitkomplexität hat BFS?

O(V + E) für V Knoten (Vertices) und E Kanten: Jeder Knoten kommt einmal in die Warteschlange und verlässt sie einmal, und jede Kante wird von beiden Enden aus geprüft. Für die Warteschlange und die Abstände braucht BFS O(V) zusätzlichen Speicher.

Warum nutzt BFS eine Warteschlange?

Weil „zuerst hinein, zuerst heraus“ die Knoten in der Reihenfolge ihrer Entdeckung hält, und das ist die Reihenfolge ihres Abstands. Mit einem Stapel würde die Suche zuerst in die Tiefe gehen: Das ist die Tiefensuche.

Findet BFS kürzeste Wege in gewichteten Graphen?

Im Allgemeinen nicht: Sie zählt Kanten, nicht ihre Längen. Für gewichtete Graphen ohne negative Kanten nehmen Sie den Dijkstra-Algorithmus. Ist jedes Gewicht 0 oder 1, funktioniert eine Variante namens 0-1-BFS.

Wo wird BFS eingesetzt?

Um Rätsel und Labyrinthe mit möglichst wenigen Zügen zu lösen, Freunde von Freunden in sozialen Netzwerken zu finden, das Web Ebene für Ebene zu durchsuchen, Nachrichten in Netzwerken zu verbreiten, und als Baustein anderer Algorithmen, etwa zur Berechnung maximaler Flüsse.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Breitensuche ausprobieren