Was ist breitensuche?

Breitensuche (auch bekannt als Breadth-First Search oder BFS) ist ein weit verbreiteter Algorithmus zur graphenbasierten Suche. Es wird verwendet, um den kürzesten Weg von einem Startknoten zu einem Zielknoten in einem Graphen zu finden.

Der BFS-Algorithmus beginnt bei einem Startknoten und besucht alle benachbarten Knoten in einer Ebene, bevor er zur nächsten Ebene übergeht. Dabei werden die Knoten in der Reihenfolge besucht, in der sie entdeckt wurden. Dieser Prozess wird fortgesetzt, bis der Zielknoten gefunden oder alle Knoten im Graphen besucht wurden.

Breitensuche ist effizient, wenn der Graph relativ flach ist und der Zielknoten nahe am Startknoten liegt. Es hat eine Zeitkomplexität von O(V+E), wobei V die Anzahl der Knoten im Graphen und E die Anzahl der Kanten im Graphen sind.