BFSDurchlauf

BFSDurchlauf, auch BFS-Durchlauf genannt, ist ein Graphen- oder Baumdurchlauf, der die Knoten in aufeinanderfolgenden Schichten vom Startknoten aus besucht. Im Gegensatz zum Tiefendurchlauf erkundet BFS alle Nachbarn eines Knotens, bevor es zu deren Nachbarn weitergeht. Dadurch ergibt sich eine Ebene‑für‑Ebene‑Besuchsreihenfolge, die dem Abstand zum Startknoten entspricht.

Funktionsweise: Der Durchlauf verwendet eine Warteschlange. Der Startknoten s wird markiert und in die Queue gelegt. Solange die Queue nicht leer ist, wird das vordere Element v entnommen, verarbeitet und alle noch nicht besuchten Nachbarn von v werden markiert und in die Queue eingefügt. Dadurch wird sichergestellt, dass Knoten mit kleiner Distanz zuerst besucht werden.

Eigenschaften und Komplexität: BFS liefert in ungewichteten Graphen kürzeste Pfade in Bezug auf die Anzahl der Kanten. Die Laufzeit beträgt O(V+E) und der Speicherbedarf O(V), primär für die Besuchsmarkierung und die Warteschlange. BFS lässt sich sowohl auf gerichtete als auch auf ungerichtete Graphen anwenden.

Anwendungen: Typische Einsatzgebiete umfassen die Bestimmung kürzester Wege in ungewichteten Graphen, Level-Order‑Besuche in Bäumen, Erkundung von Netzwerken und Social Graphs, Web-Crawling mit Begrenzung der Tiefe sowie das Finden verbundener Komponenten oder Distanzinformationen.

Varianten und Implementierung: Oft wird eine Adjazenzliste verwendet, um Speicher zu sparen. Typische Implementierungsschritte sind Initialisierung (Startknoten markieren, Queue befüllen), Schleife über die Queue, Besuch von Nachbarn und ggf. Speichern des Vorgängerspfads. Hinweis: In gewichteten Graphen liefert BFS nicht die allgemein kürzesten Pfade; hier wird Dijkstra oder eine andere Methode verwendet. Geschichte: BFS wurde in der Regel Edward F. Moore zugeschrieben.