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.

Arbeitsweise

Bei der Breitensuche wird zuerst ein Startknoten u ausgewählt. Von diesem Knoten aus wird nun jede Kante (u,v) betrachtet und getestet ob diese Kante 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 Graph 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)

Literatur

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0262531968