Was ist breitensuche?

Breitensuche (BFS)

Die Breitensuche (BFS) ist ein Algorithmus zur Traversierung oder Suche in Baum- oder Graphdatenstrukturen. Sie beginnt an der Wurzel des Graphen (oder einem beliebigen Knoten) und erkundet zuerst alle direkten Nachbarn des Knotens. Danach werden die Nachbarn dieser Nachbarn erkundet und so weiter. Im Wesentlichen wird der Graph schichtweise durchlaufen.

Kernkonzepte:

• Funktionsweise: Die Breitensuche verwendet eine Queue (Warteschlange), um die Knoten zu speichern, die als Nächstes besucht werden sollen. Sie beginnt damit, den Startknoten in die Queue einzufügen. Dann werden solange Knoten aus der Queue entnommen, besucht und deren noch nicht besuchten Nachbarn in die Queue eingefügt, bis die Queue leer ist.

• Anwendung: BFS wird häufig für die Suche nach dem kürzesten Pfad in einem ungewichteten Graphen verwendet. Andere Anwendungsbereiche sind die Suche nach allen verbundenen Komponenten eines Graphen, das Finden von Nachbarn in Peer-to-Peer-Netzwerken und die Lösung von Rätseln wie dem Labyrinthlösen.

• Vergleich zu Tiefensuche (DFS): Im Gegensatz zur Tiefensuche (DFS), die zuerst in die Tiefe des Graphen geht, bevor sie andere Zweige erkundet, geht BFS in die Breite. Dies führt zu unterschiedlichen Ergebnissen und Effizienzen je nach Problem.

• Zeitkomplexität: Die Zeitkomplexität der Breitensuche beträgt typischerweise O(V + E), wobei V die Anzahl der Knoten (Vertices) und E die Anzahl der Kanten (Edges) im Graphen ist.

• Speicherkomplexität: BFS benötigt mehr Speicher als DFS, da sie alle Knoten einer bestimmten Schicht gleichzeitig in der Queue speichern muss. Die Speicherkomplexität kann im schlimmsten Fall O(V) betragen.

• Implementierung: Die Implementierung von BFS erfolgt typischerweise mit einer Queue, einer Liste zur Verfolgung der besuchten Knoten und einer Möglichkeit, die Nachbarn eines Knotens zu ermitteln (z.B. eine Adjazenzliste oder -matrix).

• Vorteile:

  • Findet den kürzesten Pfad in ungewichteten Graphen.
  • Einfacher zu verstehen und zu implementieren als manche andere Suchalgorithmen.

• Nachteile:

  • Benötigt im Vergleich zu DFS mehr Speicher.
  • Kann in tiefen Graphen ineffizient sein, wenn nur ein bestimmtes Ziel gesucht wird, das sich möglicherweise tief im Graphen befindet.