Breitensuche
Breitensuche (englisch: breadth-first search, BFS) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen bezeichnet. Breitensuche steht im Gegensatz zur Tiefensuche (englisch: depth-first search, DFS), wobei Breitensuche im Allgemeinen speicheraufwändiger ist.
| Inhaltsverzeichnis |
Arbeitsweise
thumb|Reihenfolge im Beispielbaum Bei der Breitensuche wird zuerst ein Startknoten u ausgewählt. Von diesem Knoten aus wird nun jede Kante (u,v) betrachtet und getestet, ob der gegenüberliegende Knoten v schon entdeckt wurde. Ist dies noch nicht der Fall, so wird der entsprechende Knoten in einer Warteschlange gespeichert und im nächsten Schritt bearbeitet. Hierbei ist zu beachten, dass BFS immer zuerst alle direkt nachfolgenden Knoten bearbeitet, und nicht wie die Tiefensuche einem Pfad in die Tiefe folgt. Hier kommt auch der Name des Algorithmus her: Stellt man sich als Graph einen Baum vor, bei dem man bei der Suche mit der Wurzel beginnt, so wächst dieser Baum bei der Breitensuche immer in die Breite statt wie bei der Tiefensuche zuerst in die Tiefe. Nachdem alle Kanten des Ausgangsknotens betrachtet wurden, wird der erste Knoten der Warteschlange entnommen, und das Verfahren wiederholt.
Laufzeit
Die Laufzeit der Breitensuche ist abhängig von der Anzahl der Knoten (n) und Kanten (m) in dem Graph. Will man alle Knoten im Graphen entdecken, so beträgt die Laufzeit O(n+m).
Anwendung
Die Breitensuche kann für viele Fragestellungen in der Graphentheorie verwendet werden. Einige sind:
- Finde alle Zusammenhangskomponenten in einem Graph
- Finde alle Knoten innerhalb einer Zusammenhangskomponente
- Finde zwischen zwei Knoten u und w einen kürzesten Pfad (ungewichtete Kanten)
Die praktische Anwendung besteht zum Beispiel in der Verwendung von Routenplanern. Die Tiefensuche würde alle Knoten Stück für Stück abarbeiten und dann sämtliche errechneten mögliche Wege hinsichtlich ihrer Länge überprüfen und den kürzesten Weg ausgeben. Die Breitensuche dagegen hat den kürzesten Weg gefunden, sobald der erste errechnete Weg sein Ziel erreicht hat.
Literatur
- Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, 2nd edition 2001, ISBN 0262531968