Breitensuche - ein Algorithmus

(Formulierung nach Westphal)

Gesucht: kürzester Weg (bzgl. Kantenzahl) vom Startknoten zu allen anderen Knoten.

1. Wähle einen Startknoten
2. Markiere alle Kanten, die von diesem Knoten ausgehen
3. Schreibe alle Nachbarknoten des Startknoten in eine Liste ¹⁾
4. Streiche den ersten Knoten aus der Liste
5. Markiere alle von diesem Knoten ausgehenden Kanten, sofern sie noch nicht markiert sind , und nicht im Endknoten auf bereits markierte Kanten treffen, mit neuer Farbe
6. Schreibe alle Knoten, die am Ende dieser neu markierten Kanten sind, hinten an die Liste
7. Wiederhole 4., 5. und 6. so lange, bis die Liste leer ist.