Breitensuche

Grundidee der Breitensuche

Die Breitensuche (englisch breadth-first search, BFS) ist ein uninformierter Suchalgorithmus zum Durchsuchen oder Durchlaufen der Knoten eines Graphen. Sie beginnt bei einem Startknoten und untersucht den Graphen Ebene für Ebene: Zuerst werden alle direkt erreichbaren Knoten betrachtet, danach deren Folgeknoten. Anders als die Tiefensuche verfolgt sie also nicht zunächst einen einzelnen Pfad möglichst weit.

Ein Knotenabstand ist die Zahl der Kanten auf dem Weg vom Startknoten zu einem Knoten. Der Iterationsschritt entspricht diesem Abstand. In einem zusammenhängenden Graphen hängt die Zahl der Iterationsschritte vom gewählten Startknoten ab. Bei nicht zusammenhängenden Graphen sind Knotenabstand und Iterationsschritte nur innerhalb einer Zusammenhangskomponente definiert. In gerichteten Graphen muss der Abstand nicht symmetrisch sein: Der Abstand von A nach B kann sich vom Abstand von B nach A unterscheiden.

Ablauf mit Warteschlange

Zuerst wird ein Startknoten u gewählt. Für jede Kante (u,v) wird geprüft, ob der gegenüberliegende Knoten v bereits entdeckt wurde oder das gesuchte Element ist. Noch nicht entdeckte Knoten werden markiert und in einer Warteschlange gespeichert. Nachdem alle Kanten des aktuellen Knotens betrachtet wurden, wird der vorderste Knoten der Warteschlange entnommen und auf dieselbe Weise bearbeitet.

Die Warteschlange sorgt für die Reihenfolge: Knoten einer Ebene werden vollständig bearbeitet, bevor Knoten der nächsten Ebene folgen. Im Städtebeispiel mit Hannover als Startknoten lautet die Ebenenfolge: Iterationsschritt 0 Hannover; Iterationsschritt 1 Frankfurt, Hamburg, Berlin; Iterationsschritt 2 Zürich, Stuttgart, Mannheim, Wien; Iterationsschritt 3 München, Dresden. Die genaue Durchlaufreihenfolge kann sich bei einem anderen Startknoten oder bei einem nicht symmetrischen gerichteten Graphen ändern.

Algorithmus und Umsetzung

Der Algorithmus markiert den Startknoten als gesehen und legt ihn in eine Warteschlange. Solange die Warteschlange nicht leer ist, wird ihr erster Knoten entnommen. Ist dieser der Zielknoten, endet die Suche mit „gefunden“. Andernfalls werden alle bisher unmarkierten Nachfolger an das Ende der Warteschlange gehängt und zugleich als gesehen markiert. Wird die Warteschlange leer, wurden alle erreichbaren Knoten untersucht; dann lautet das Ergebnis „nicht gefunden“.

Eine rekursive Form kann mit einer Menge fringe der Knoten der aktuellen Ebene und einer Menge gesehen formuliert werden. Die Schleifenform nutzt direkt eine Warteschlange. Zusätzlich zum Wahrheitswert für das Finden können in praktischen Anwendungen etwa aktuelle Pfadtiefe oder bisheriger Suchweg gespeichert werden.

In der gezeigten C#-Umsetzung besitzt jeder Knoten eine Liste adjacentNodes seiner Nachbarn. Eine Queue<Node> verwaltet die noch zu bearbeitenden Knoten, ein HashSet<Node> visitedNodes die markierten Knoten und eine Liste traversedNodes die Reihenfolge der besuchten Knoten. Die Nachbarn sind als Liste gespeichert, damit die Reihenfolge eindeutig ist und die Ebenen von links nach rechts durchlaufen werden. Bei einer Menge ist diese Reihenfolge nicht zwingend festgelegt. Statt eines HashSet können auch eine Liste oder ein bool-Array verwendet werden.

Aufwand und Vollständigkeit

Mit |V| als Anzahl der Knoten und |E| als Anzahl der Kanten beträgt der Speicherplatzverbrauch in Landau-Notation 𝒪(|V|), weil alle bisher entdeckten Knoten gespeichert werden. Deshalb ist die Breitensuche für Verfahren, in denen Knoten erst während der Suche erzeugt werden, etwa Branch & Bound, wegen des großen Speicherbedarfs meist ungeeignet. Die iterative Tiefensuche ist ein ähnliches Verfahren, das meist deutlich weniger Speicher benötigt.

Die Laufzeit beträgt im ungünstigsten Fall 𝒪(|V|+|E|). Dabei kann 𝒪(|E|), abhängig von der Dichte des Graphen, zwischen 𝒪(1) und 𝒪(|V|²) liegen. Wenn die Knotenzahl vorher bekannt ist und zusätzliche Datenstrukturen festhalten, welche Knoten bereits in die Warteschlange aufgenommen wurden, bleibt die Platzkomplexität 𝒪(|V|), zusätzlich zum Speicher für die Graphdarstellung.

Existieren an jedem Knoten nur endlich viele Alternativen, ist die Breitensuche vollständig: Falls eine Lösung existiert, wird sie gefunden. Bei einem unendlichen Graphen ohne Lösung divergiert sie jedoch. Bei implizit dargestellten unendlichen Graphen findet sie schließlich einen existierenden Zielzustand, während die Tiefensuche sich in einem zielosen Teil des Graphen verlieren kann.

Optimalität und Anwendungen

Eine mit Breitensuche gefundene Lösung besitzt den kürzesten Abstand zum Wurzel- beziehungsweise Startknoten. Bei gewichteten Kanten muss ein Pfad mit wenigen Kanten aber nicht die geringsten Pfadkosten haben. Sind alle Kantengewichte äquivalent, ist jede gefundene Lösung optimal. Für gewichtete Kanten kann die Breitensuche zur uniformen Kostensuche erweitert werden. Diese besucht Knoten in Reihenfolge steigender Pfadkosten vom Wurzelknoten und verwendet üblicherweise eine Vorrangwarteschlange; ihre Optimalität ist nur bei nicht-negativen Kantengewichten garantiert.

Anwendungen sind das Finden aller Knoten einer Zusammenhangskomponente, das Prüfen, ob ein Graph paar ist, einschließlich einer möglichen zulässigen 2-Färbung, das Finden eines kürzesten Pfads zwischen zwei Knoten u und w bei ungewichteten Kanten sowie das Kürzeste-Kreise-Problem.