# Breitensuche

Breitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Im Gegensatz zur Tiefensuche werden zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten (siehe Abbildung).

## Arbeitsweise

Die Breitensuche ist eine uninformierte Suche, welche durch Expansion der einzelnen Level der Graphen ausgehend vom Startknoten den Graph in die Breite nach einem Element durchsucht.
Zuerst wird ein Startknoten $u$ ausgewählt. Von diesem Knoten aus wird nun jede Kante $(u,v)$ betrachtet und getestet, ob der gegenüberliegende Knoten $v$ schon entdeckt wurde bzw. das gesuchte Element ist. Ist dies noch nicht der Fall, so wird der entsprechende Knoten in einer Warteschlange gespeichert und im nächsten Schritt bearbeitet. Hierbei ist zu beachten, dass Breitensuche immer zuerst alle Knoten der gleichen Ebene bearbeitet, und nicht wie die Tiefensuche einem Pfad in die Tiefe folgt. Nachdem alle Kanten des Ausgangsknotens betrachtet wurden, wird der erste Knoten der Warteschlange entnommen und das Verfahren wiederholt.
| Eine graphentheoretische Landkarte von Deutschland, Österreich und der Schweiz mit den Verbindungen zwischen einigen Städten. Dieses Beispiel ist ein ungerichteter Graph mit 10 Knoten. | Der Baum, welcher entsteht, wenn man Breitensuche auf die Landkarte anwendet und in Hannover startet. Dieser Baum hat die Höhe 4. Daher hat die Breitensuche in diesem Fall 4 Iterationsschritte. |
Der Index des Iterationsschritts in der while-Schleife (siehe unten) entspricht dabei dem Knotenabstand des aktuell durchlaufenen Knotens vom Startknoten. Dieser Index müsste, um zum Beispiel auf der Konsole ausgegeben zu werden, in einer Variablen gespeichert werden.
Im Beispiel mit den Städten (siehe oben) gibt es 4 Iterationsschritte:
* 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)
Der Knotenabstand bezieht sich immer auf den Startknoten. Im links dargestellten ungerichteten Graphen ist es Hannover. Bei gerichteten Graphen ist der Knotenabstand zwischen zwei verschiedenen Knoten nicht unbedingt symmetrisch.
In einem gerichteten Graphen könnte zum Beispiel der Knotenabstand von Hannover nach Mannheim ebenfalls 2 sein. Der Knotenabstand von Mannheim nach Hannover jedoch könnte gleich 1 sein, wenn es eine Kante (direkte Verbindung) von Mannheim nach Hannover gäbe. Er könnte auch gleich 2, gleich 3 oder größer sein.
Der Knotenabstand und die Anzahl der Iterationsschritte ist nur für zusammenhängende Graphen definiert und hängt vom Startknoten ab. Für nicht zusammenhängende Graphen ist der Knotenabstand und die Anzahl der Iterationsschritte nur innerhalb jeder Zusammenhangskomponente definiert.
Hinweis: Der in der Abbildung links oben mit den Städten gezeigte Graph ist ein ungerichteter Graph. Die Reihenfolge der durchlaufenen Knoten kann sich ändern, wenn stattdessen ein anderer Startknoten oder ein gerichteter Graph genommen wird, der nicht symmetrisch ist.

## Algorithmus

* Bestimme den Knoten, an dem die Suche beginnen soll, markiere ihn als gesehen und speichere ihn in einer Warteschlange ab.
* Entnimm einen Knoten vom Beginn der Warteschlange.
** Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere „gefunden“ zurück.
** Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange an und markiere sie als gesehen.
* Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere „nicht gefunden“ zurück.
* Wiederhole Schritt 2.
Nachstehend formulierte Algorithmen sind als Pseudocode zu verstehen und geben aus Gründen der Lesbarkeit nur an, ob der Zielknoten gefunden wurde. Weitere, in Anwendungsfällen wichtige Informationen – wie z. B. die aktuelle Pfadtiefe oder der bisherige Suchweg – könnten zusätzlich eingefügt werden.
Rekursiv formuliert:
Als Schleife formuliert:

## Programmierung

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung der Breitensuche für einen gerichteten Graphen. Der gerichtete Graph wird als Klasse DirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die die Liste der markierten Knoten auf der Konsole ausgibt.
Hinweise: Für die Nachbarknoten wurde eine Liste als Datentyp verwendet, damit die Reihenfolge der durchlaufenen Knoten eindeutig ist und die Knoten in allen Ebenen von links nach rechts durchlaufen werden. Für den Datentyp Menge zum Beispiel muss das nicht der der Fall sein. Statt dem HashSet (Menge) visitedNodes kann auch eine Liste oder ein Array vom Typ bool (Boolesche Variable) verwendet werden, wie im Einzelnachweis gezeigt.
Der in der Abbildung links oben mit den Städten gezeigte Graph ist ein ungerichteter Graph. Die Reihenfolge der durchlaufenen Knoten kann sich ändern, wenn stattdessen ein anderer Startknoten oder ein gerichteter Graph genommen wird, der nicht symmetrisch ist.

## Eigenschaften

Bezeichne $|V|$ die Anzahl der Knoten und $|E|$ die Anzahl der Kanten im Graphen. Speicherplatzverbrauch und Laufzeit des Algorithmus sind in Landau-Notation angegeben.

### Speicherplatzverbrauch

Da alle bisher entdeckten Knoten gespeichert werden, beträgt der Speicherplatzverbrauch von Breitensuche ${\mathcal {O}}(|V|)$. Die Breitensuche ist für Verfahren, bei denen die Knoten erst während der Breitensuche generiert werden (z. B. das Branch-&-Bound-Verfahren), aufgrund des großen Platzverbrauches meist ungeeignet. Ein der Breitensuche ähnliches Verfahren, das jedoch meist mit deutlich weniger Speicher auskommt, ist die iterative Tiefensuche.

### Laufzeit

Da im ungünstigsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit der Breitensuche ${\mathcal {O}}(|V|+|E|)$. Beachte, dass ${\mathcal {O}}(|E|)$ zwischen ${\mathcal {O}}(1)$ und ${\mathcal {O}}(|V|^{2})$ variieren kann, abhängig davon, wie dünn der Graph ist.
Wenn die Anzahl der Knoten im Graphen im Voraus bekannt ist und zusätzliche Datenstrukturen verwendet werden, um zu bestimmen, welche Knoten bereits zur Warteschlange hinzugefügt wurden, kann die Platzkomplexität als ${\mathcal {O}}(|V|)$ ausgedrückt werden. Dies gilt zusätzlich zu dem für das Graphen selbst erforderlichen Speicherplatz, der abhängig von der von einer Implementierung des Algorithmus verwendeten Graphendarstellung variieren kann.

### Vollständigkeit

Wenn in jedem Knoten nur endlich viele Alternativen existieren, ist die Breitensuche vollständig. Dies bedeutet, dass, wenn eine Lösung existiert, diese auch gefunden wird. Dies ist unabhängig davon, ob der zugrunde liegende Graph endlich ist oder nicht. Sollte jedoch keine Lösung existieren, so divergiert die Breitensuche bei einem unendlichen Graphen.
Bei der Analyse von Algorithmen wird angenommen, dass die Eingabe für die Breitensuche ein endlicher Graph ist, der explizit als Adjazenzliste oder ähnlich dargestellt wird. Bei der Anwendung von Graph-Traversierungen in der künstlichen Intelligenz kann die Eingabe jedoch eine implizite Darstellung eines unendlichen Graphen sein. In diesem Zusammenhang wird ein Suchverfahren als vollständig beschrieben, wenn garantiert wird, dass ein Zielzustand gefunden wird, falls einer existiert. Die Breitensuche ist abgeschlossen, die Tiefensuche jedoch nicht. Bei Anwendung auf unendlich viele Graphen, die implizit dargestellt werden, findet die Breitensuche schließlich den Zielzustand, aber die Tiefensuche kann in Teilen des Graphen verloren gehen, die keinen Zielzustand haben und niemals zurückkehren.

### Optimalität

Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Wurzelknoten. Führt man Kantengewichte ein, so muss das Ergebnis, welches am nächsten zum Startknoten liegt, nicht notwendigerweise auch das Ergebnis mit den geringsten Pfadkosten sein. Dieses Problem umgeht man, indem man die Breitensuche zur uniformen Kostensuche erweitert. Sind jedoch alle Kantengewichte äquivalent, so ist jede durch Breitensuche gefundene Lösung optimal, da in diesem Fall die Lösung, die am nächsten zum Ausgangsknoten liegt, auch die Lösung mit den geringsten Kosten ist. Ob existierende Lösungen überhaupt gefunden werden hängt mit Endlichkeitseigenschaften des Suchbaums zusammen (siehe Vollständigkeit).
Die uniforme Kostensuche (englisch uniform-cost search) ist eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Der Algorithmus besucht Knoten in Reihenfolge aufsteigender Pfadkosten vom Wurzelknoten und wird deshalb üblicherweise mit einer Vorrangwarteschlange implementiert, in der alle noch nicht besuchten Nachbarn bereits besuchter Knoten mit der Pfadlänge als Schlüssel verwaltet werden. Die Optimalität ist nur für nicht-negative Kantengewichte garantiert.

## Anwendung

Die Breitensuche kann für viele Fragestellungen in der Graphentheorie verwendet werden. Einige sind:
* Finde alle Knoten innerhalb einer Zusammenhangskomponente
* Prüfe, ob der gegebene Graph paar ist und finde ggf. eine zulässige 2-Färbung seiner Knoten
* Finde zwischen zwei Knoten u und w einen kürzesten Pfad (ungewichtete Kanten)
* Kürzeste-Kreise-Problem