Breitensuche (BFS)
Durchsucht einen Graphen Schicht für Schicht. Eine Warteschlange bestimmt den nächsten Knoten, deshalb kommen die nächstgelegenen Knoten immer zuerst dran.
- Zeit O(V + E)
- Speicher O(V)
- nutzt eine Warteschlange
Was bedeutet das?
- Knoten: ein Punkt des Graphen, hier als Kreis mit einem Buchstaben gezeichnet.
- Kante: eine Linie, die zwei Knoten verbindet. Hier kann man sie in beide Richtungen entlanggehen.
- Nachbarn: die Knoten, die über eine Kante mit einem Knoten verbunden sind. Sie werden in alphabetischer Reihenfolge geprüft.
- Warteschlange: Wer zuerst kommt, geht zuerst. BFS nimmt immer den Knoten, der am längsten gewartet hat.
- Stapel: Was zuletzt hinzukommt, geht zuerst. DFS macht immer beim zuletzt erreichten Knoten weiter.
- V und E: die Anzahl der Knoten (vertices) und Kanten (edges). O(V + E) heißt: Jeder Knoten und jede Kante wird nur konstant oft bearbeitet.
- in der Warteschlange
- aktuell
- erledigt
- Kante des Suchbaums
- übersprungene Kante
Start bei A. Auf Abspielen drücken oder die Suche Schritt für Schritt durchgehen.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
Probieren Sie es aus: Wählen Sie den Graphen mit zwei Teilen. Die Knoten, die nicht mit dem Start verbunden sind, werden nie erreicht.
So funktioniert es
Die Breitensuche legt den Startknoten in eine Warteschlange. Dann nimmt sie immer wieder den Knoten vorne aus der Warteschlange und hängt seine neuen Nachbarn hinten an. Eine Warteschlange bedient in der Reihenfolge der Ankunft. Deshalb sind alle Knoten, die eine Kante entfernt liegen, erledigt, bevor ein Knoten zwei Kanten entfernt drankommt. Die Zahl neben einem Knoten ist sein Abstand zum Start: die kleinste Anzahl von Kanten, über die man ihn erreicht.
Wann es sich eignet
Nutzen Sie die Breitensuche, wenn Sie den kürzesten Weg in Schritten brauchen: die wenigsten Züge in einem Rätsel, die wenigsten Sprünge in einem Netzwerk, die Menschen, die höchstens zwei Kontakte von Ihnen entfernt sind. Bei einem großen Graphen kann die Warteschlange lang werden, weil sie eine ganze Schicht auf einmal enthält.