BFS (Breitensuche)
Graph-Traversierung, die alle Knoten einer Tiefe besucht, bevor sie zur nächsten übergeht. Implementiert mit einer FIFO-Queue.
Garantiert den kürzesten Weg in einem ungewichteten Graphen. Klassische Anwendungen: kleinste Anzahl Hops zwischen Knoten finden (LinkedIns "3 Grade"), Web-Crawling, Level-Order-Traversierung von Bäumen, Spiele-KI nach dem Prinzip "Sieg in möglichst wenigen Zügen".
Zeitkomplexität O(V+E), Platzbedarf im schlechtesten Fall O(V). Konkurrenz: DFS (Stack statt Queue, geht zuerst in die Tiefe), Dijkstra (bei gewichteten Kanten).