Breitensuche (BFS): Ablauf und kürzeste Wege

Ein Graph besteht aus Knoten (den Punkten) und Kanten (den Verbindungen zwischen den Knoten). Die Breitensuche (englisch breadth-first search, kurz BFS) durchläuft die Knoten eines Graphen. Sie bearbeitet immer zuerst alle Knoten der gleichen Ebene. Anders als die Tiefensuche folgt sie nicht einem Pfad in die Tiefe.

Dafür braucht sie eine Warteschlange. Mit enqueue legst du ein Objekt hinein, mit dequeue holst du eines zurück und entfernst es. Die Warteschlange arbeitet nach dem FIFO-Prinzip: Das Objekt, das zuerst hineingelegt wurde, kommt zuerst wieder heraus. Das ist wie an einer Kasse: Wer sich zuerst anstellt, wird zuerst bedient.

Der Ablauf: Im ersten Schritt wählst du den Startknoten, markierst ihn als gesehen und speicherst ihn in der Warteschlange. Im zweiten Schritt nimmst du einen Knoten vom Beginn der Warteschlange. Alle bisher unmarkierten Nachfolger dieses Knotens hängst du ans Ende der Warteschlange an und markierst sie dabei als gesehen. In einem ungerichteten Graphen sind die Nachfolger die Nachbarn. Dann wiederholst du den zweiten Schritt. Findest du das gesuchte Element, brichst du ab. Ist die Warteschlange leer, endet die Suche mit „nicht gefunden“.

Unser Beispielgraph ist ungerichtet. Die Nachbarn stehen in dieser Reihenfolge in der Eingabe: A: D, B, C; B: A, E, F; C: A, G; D: A, H; E: B; F: B, H; G: C; H: D, F. Start ist A. Diese Reihenfolge ist eine Wahl der Aufgabe, keine Regel der Breitensuche.

Die Breitensuche arbeitet Ebene für Ebene. Der Startknoten ist Ebene 0. Der Knotenabstand gibt an, über wie viele Kanten ein Knoten vom Startknoten entfernt ist. Im Beispielgraphen ist der Abstand von A zu D 1 Kante, von A zu H 2 Kanten und von A zu G 2 Kanten. Der Knotenabstand bezieht sich immer auf den Startknoten.

Ein zweites Beispiel ist ein Städtegraph mit Start Hannover. Dort werden die Iterationsschritte Ebene für Ebene gezählt, und der Index des Iterationsschritts entspricht dem Knotenabstand. Iterationsschritt 0: Hannover (Knotenabstand 0). Iterationsschritt 1: Frankfurt, Hamburg, Berlin (Knotenabstand 1). Iterationsschritt 2: Zürich, Stuttgart, Mannheim, Wien (Knotenabstand 2). Iterationsschritt 3: München, Dresden (Knotenabstand 3). Achtung: Hier ist ein Schritt eine ganze Ebene. Im Ablauf des ersten Beispiels (Start A) ist dagegen jede Zeile nur eine einzelne Entnahme aus der Warteschlange. Die Nummer der Entnahme ist nicht der Abstand: D wird als Zweiter entnommen, hat aber Abstand 1.

Bei gerichteten Graphen ist der Knotenabstand zwischen zwei verschiedenen Knoten nicht unbedingt symmetrisch. Bei einem nicht zusammenhängenden Graphen ist der Knotenabstand nur innerhalb jeder Zusammenhangskomponente definiert (das ist ein Teil des Graphen, dessen Knoten miteinander verbunden sind), also nur für Knoten, die vom Startknoten aus erreichbar sind.

Den Vorgänger eines Knotens notierst du so: Es ist der Knoten, von dem aus er entdeckt wurde. Im Beispielgraphen ist A der Vorgänger von D, B und C. Der Vorgänger von H ist D, der Weg zu H ist A → D → H. Den Weg zu einem Knoten erhältst du als Kette der Vorgänger von A bis zu diesem Knoten. Verbindest du jeden Knoten außer dem Startknoten mit dem Knoten, von dem aus er gefunden wurde, entsteht der Breitensuchbaum.

Die Breitensuche durchsucht dem Startknoten näher gelegene Knoten vor weiter entfernten. Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Wurzelknoten, also zum Startknoten. Sie kann zwischen zwei Knoten einen kürzesten Pfad finden, wenn die Kanten ungewichtet sind.

Ein Kantengewicht ist eine Zahl an einer Kante, die zum Beispiel Kosten oder eine Länge angibt. Sind alle Kantengewichte gleich, so ist jede durch Breitensuche gefundene Lösung optimal: In diesem Fall ist die Lösung, die am nächsten zum Ausgangsknoten liegt, auch die mit den geringsten Kosten. Bei verschiedenen Gewichten muss das Ergebnis, das am nächsten zum Startknoten liegt, nicht unbedingt das Ergebnis mit den geringsten Pfadkosten sein. Dafür gibt es die uniforme Kostensuche, eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Ihre Optimalität ist nur für nicht-negative Kantengewichte garantiert.

Den Weg selbst erhältst du, wenn du dir den bei der Suche gegangenen Weg speicherst. In einem Irrgarten sind die Zellen die Knoten. Für jede besuchte Zelle merkst du dir ihre Entfernung vom Startpunkt oder die Nachbarzelle, von der aus sie betreten wurde. Den kürzesten Lösungsweg erhältst du, indem du vom Zielpunkt aus die besuchten Zellen zurück bis zum Startpunkt verfolgst.

Warum die Ebenenreihenfolge das garantiert, wird hier nicht Schritt für Schritt bewiesen. Merke dir die Aussage und ihre Bedingung.

Die Laufzeit der Breitensuche beträgt O(|V|+|E|). Dabei ist |V| die Anzahl der Knoten und |E| die Anzahl der Kanten. Die Schreibweise O(…) heißt Landau-Notation. Sie gibt an, wie die Anzahl der Schritte oder der Speicherplatz von der Größe des Problems abhängt. Für diese Analyse wird angenommen, dass die Eingabe ein endlicher Graph ist, der explizit als Adjazenzliste oder ähnlich dargestellt wird. Eine Adjazenzliste gibt für jeden Knoten eine Liste aller seiner Nachbarn an, bei gerichteten Graphen seiner Nachfolger. Wie groß |E| ist, hängt davon ab, wie dünn der Graph ist: O(|E|) kann zwischen O(1) und O(|V|²) liegen.

Der Speicherplatzverbrauch beträgt O(|V|), weil alle bisher entdeckten Knoten gespeichert werden. Das gilt, wenn die Anzahl der Knoten im Voraus bekannt ist und man sich merkt, welche Knoten schon in der Warteschlange waren. Es kommt zusätzlich zu dem Platz hinzu, den der Graph selbst braucht. Vermische das nicht mit der Laufzeit.

Grenzen: Für Verfahren, bei denen die Knoten erst während der Suche erzeugt werden (zum Beispiel Branch-&-Bound), ist die Breitensuche wegen des großen Platzverbrauchs meist ungeeignet. Die iterative Tiefensuche kommt meist mit deutlich weniger Speicher aus. Bei Kantengewichten liefert die Breitensuche nicht unbedingt den billigsten Weg.

Hat jeder Knoten nur endlich viele Alternativen, ist die Breitensuche vollständig. Wenn eine Lösung existiert, wird sie gefunden, auch in einem unendlichen Graphen. Existiert keine Lösung, divergiert die Breitensuche bei einem unendlichen Graphen: Sie kommt dann zu keinem Ergebnis.