Breitensuche

Die Breitensuche (BFS) durchläuft einen Graphen ausgehend von einem Startknoten $v$ schichtweise. Zuerst werden alle direkten Nachbarn besucht, dann deren Nachbarn usw..

Wichtiger Vorteil:

• Der Pfad vom Startknoten $v$ zu einem beliebigen Knoten $u$ im resultierenden BFS-Baum ist immer ein kürzester Pfad im ursprünglichen Graphen $G$.
• Die Distanz $dis{t}_G(v,u)$ entspricht der Tiefe des Knotens im BFS-Baum.

Links

• SSSP
• Distanz
• DS_vollständiger_foliensatz.pdf