Die Breitensuche (englisch Breadth-First Search, kurz BFS) ist ein Algorithmus zum Durchsuchen von Graphen und Bäumen. Anders als die Tiefensuche erkundet sie die Knoten Ebene für Ebene: Zuerst alle direkten Nachbarn des Startknotens, dann deren Nachbarn, dann die nächste Ebene – bis alle erreichbaren Knoten besucht sind. Sie findet dadurch in ungewichteten Graphen immer den kürzesten Weg in Kantenzahl.
Wie funktioniert die Breitensuche?
Die Breitensuche arbeitet mit einer Warteschlange (Queue) nach dem FIFO-Prinzip (First In, First Out):
- Der Startknoten kommt als Erstes in die Queue und wird als besucht markiert.
- Solange die Queue nicht leer ist, wird der vorderste Knoten entnommen und betrachtet.
- Alle unbesuchten Nachbarn dieses Knotens kommen ans Ende der Queue; jeder erhält die Distanz des aktuellen Knotens plus eins.
- Durch das FIFO-Prinzip werden genau die Knoten der Ebene n verarbeitet, bevor die Knoten der Ebene n+1 an der Reihe sind.
Ein markantes Beispiel: Bei einem Schachbrett-Springerproblem oder in einem sozialen Netzwerk kann man mit BFS die minimale Anzahl an Schritten beziehungsweise den Grad der Trennung zwischen zwei Personen bestimmen.
Laufzeit und Speicher
Wie die Tiefensuche besucht auch die Breitensuche jeden Knoten und jede Kante höchstens einmal: Die Laufzeit beträgt O(V + E) bei V Knoten und E Kanten. Der Speicherbedarf ist allerdings höher als bei DFS, denn die Queue kann im schlimmsten Fall eine ganze Ebene des Graphen enthalten – bis zu O(V) Knoten. Bei sehr breiten Graphen kostet das entsprechend Speicher.
Typische Anwendungen
- Kürzeste Wege in ungewichteten Graphen: Netzwerk-Routing ohne Kosten, minimale Anzahl von Hops oder Zügen.
- Web-Crawler: Suchmaschinen folgen Links von einer Seite aus Ebene für Ebene, um das Web systematisch zu durchsuchen.
- Soziale Netzwerke: Empfehlungen von Freunden, gemeinsame Gruppen und der Grad der Trennung („Freunde von Freunden“).
- P2P-Netze und Broadcast: Nachrichten oder Dateien verbreiten sich in einem Peer-to-Peer-Netzwerk Schritt für Schritt über die Nachbarn.
- GPS-Navigation auf ungewichteten Wegnetzen: BFS liefert die Route mit den wenigsten Straßen; gewichtete Netze übernimmt der Dijkstra-Algorithmus.
Abgrenzung zur Tiefensuche
Die Breitensuche bevorzugt die Nähe zum Startknoten: Sie ist die richtige Wahl, wenn der kürzeste Weg zählt oder wenn die Ziele dicht beim Start liegen. Die Tiefensuche benötigt weniger Speicher und eignet sich für vollständiges Durchsuchen, Backtracking und die Fragen nach Zyklen oder topologischer Ordnung. Beide Strategien zusammen sind die Grundlage der Traversierung und werden oft kombiniert, etwa wenn eine Breitensuche zuerst das Grobgerüst liefert und eine Tiefensuche danach Details erschließt.
Verwandte Grundlagen: Graph-Datenstruktur | Queue | Dijkstra-Algorithmus | Tiefensuche | Big-O-Notation