How it works?

BFS verwendet eine besucht-Markierung pro Knoten und eine Warteschlange von zu verarbeitenden Knoten.

Schritt-für-Schritt-Prozess:

1. Markiere den Startknoten als besucht und füge ihn der Warteschlange hinzu.
2. Entferne den vordersten Knoten aus der Warteschlange und notiere ihn in der Besuchsreihenfolge.
3. Markiere für jeden unbesuchten Nachbarn (aufsteigend) diesen als besucht und füge ihn der Warteschlange hinzu. Das Markieren beim Hinzufügen zur Warteschlange verhindert, dass ein Knoten doppelt hinzugefügt wird.
4. Wiederhole den Vorgang, bis die Warteschlange leer ist.

Beispiel für die Knoten 0..3 mit den Kanten [0,1, 0,2, 1,3, 2,3], beginnend bei 0:

• Besuche 0, füge 1 und 2 der Warteschlange hinzu; besuche 1, füge 3 der Warteschlange hinzu; besuche 2; besuche 3.
• Besuchsreihenfolge: [0, 1, 2, 3] (vergleiche mit DFS: [0, 1, 3, 2]).