Informatik

Wie funktioniert Breitensuche?

Breitensuche (Breadth-First Search, BFS) ist ein algorithmisches Verfahren zur Durchsuchung von Graphen. Es exploriert alle Nachbarn eines Knotens, bevor es in die Tiefe geht. BFS wird häufig verwendet, um den kürzesten Pfad in ungewichteten Graphen zu finden.

Algorithmus

• Starte beim Wurzelknoten oder einem beliebigen Knoten.
• Verwende eine Warteschlange zur Speicherung der Knoten, die besucht werden sollen.
• Besuche einen Knoten, markiere ihn als besucht, und füge alle seine unbesuchten Nachbarn zur Warteschlange hinzu.
• Wiederhole, bis die Warteschlange leer ist.

Pseudocode

BFS(start):
    erstelle eine leere Warteschlange Q
    markiere start als besucht
    füge start der Warteschlange Q hinzu

    solange Q nicht leer ist:
        aktuell = entferne das vorderste Element von Q
        markiere aktuell als besucht

        für jeden Nachbarn von aktuell:
            falls Nachbar nicht besucht ist:
                markiere Nachbar als besucht
                füge Nachbar der Warteschlange Q hinzu

Beispiel

Gegeben sei der Graph:

Starte bei Knoten $A$. Die Reihenfolge der Besuche ist: $A, B, C, D, E$.