Overview
BFS erkundet einen Graphen ebenenweise von der Quelle aus und findet kürzeste Pfade auf ungewichteten Graphen.
Analogy
Stein ins Wasser werfen: Wellen breiten sich gleichmäßig nach außen aus – erst nahe Knoten, dann ferne.
Step-by-step
- Initialisiere Queue mit Startknoten; markiere als besucht.
- Solange Queue nicht leer: dequeue Knoten u.
- Für jeden Nachbar v von u: wenn nicht besucht → markiere, enqueue, parent[v]=u.
- Tiefe (Schritt) entspricht Anzahl Queue-Entleerungen.
Visual
Graph: 1-2, 1-3, 2-4. BFS von 1: Ebene 0=[1]; Ebene 1=[2,3]; Ebene 2=[4]
Common mistakes
- Knoten vor dem Enqueuen als besucht markieren – nicht nach dem Dequeuen (doppeltes Enqueuing).
- Für Kurzestpfad: Distanz beim Enqueuen inkrementieren.
Practice questions
- Kürzesten Pfad in ungewichtetem Graphen mit BFS finden.
- Bipartitheit eines Graphen mit BFS-Einfärbung prüfen.
Space
O(V) für Queue und visited-Set