Mit Google fortfahren
Breitensuche (BFS): Ablauf und kürzeste Wege
Die Breitensuche, kurz BFS für Breadth-first search, durchsucht einen Graphen vom Startknoten aus Schicht für Schicht. Eine FIFO-Warteschlange sorgt dafür, dass zuerst nahe und danach weiter entfernte Knoten bearbeitet werden.
Auf dieser Seite lernst du, eine Breitensuche auszuführen, ihre Besuchsreihenfolge zu dokumentieren und kürzeste Wege in ungewichteten Graphen zu bestimmen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie entstehen die BFS-Schichten?
Stell dir ein Netzwerk aus Orten und Verbindungen vor. Du startest an einem Ort und möchtest systematisch alle erreichbaren Orte untersuchen. Die Breitensuche betrachtet zuerst alle direkten Nachbarn, dann deren noch unbesuchte Nachbarn und so weiter.
Graph
Ein Graph besteht aus Knoten und Kanten. Knoten stellen Objekte dar; Kanten beschreiben Verbindungen zwischen ihnen. Bei einem gerichteten Graphen darfst du eine Kante nur in Pfeilrichtung durchlaufen.
Der Startknoten liegt auf Ebene 0. Seine noch unentdeckten Nachbarn liegen auf Ebene 1. Knoten, die erstmals von Ebene 1 aus erreicht werden, liegen auf Ebene 2. So entstehen Schichten mit wachsendem Abstand zum Start.
Die genaue Reihenfolge innerhalb einer Ebene kann von der Reihenfolge der Nachbarn abhängen. Die Ebenennummern ändern sich dadurch nicht.
BFS bearbeitet alle Knoten einer Ebene, bevor sie zur nächsten Ebene übergeht.
Wie arbeitet die Warteschlange?
Angenommen, mehrere entdeckte Knoten warten noch auf ihre Bearbeitung. BFS verwaltet sie mit einer FIFO-Warteschlange: Wer zuerst eingefügt wurde, wird zuerst entnommen. FIFO bedeutet „First in, first out“.
Ein Knoten durchläuft drei Zustände:
- unentdeckt: Er wurde noch nicht gefunden.
- entdeckt: Er ist markiert und wartet in der Warteschlange.
- abgearbeitet: Er wurde entnommen; seine Nachbarn wurden untersucht.
Der Ablauf lautet:
- Markiere den Startknoten und füge ihn in die Warteschlange ein.
- Entnimm den vordersten Knoten
u. - Untersuche nacheinander seine Nachfolger.
- Markiere jeden noch unentdeckten Nachfolger
vsofort und füge ihn hinten ein. - Speichere bei Bedarf
d[v] = d[u] + 1und den Vorgängerπ[v] = u. - Wiederhole den Ablauf, bis das Ziel gefunden oder die Warteschlange leer ist.
Das sofortige Markieren beim Einfügen ist entscheidend. Es verhindert, dass mehrere Kanten denselben Knoten mehrfach in die Warteschlange bringen. Auch Rückkanten, Kreise und Selbstschleifen führen dann nicht zu endlosen Wiederholungen.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Ein neu entdeckter Knoten wird sofort . Der nächste Knoten wird entnommen. Neue Knoten kommen an das der FIFO-Warteschlange.
Wie sieht ein vollständiger Durchlauf aus?
Wir verwenden den gerichteten Graphen mit diesen Kanten:
A → BA → CB → CC → AC → DD → D
Die Nachbarn werden in der angegebenen Reihenfolge betrachtet. Startknoten ist C.
- Markiere
C. Warteschlange:C. Distanz:d[C] = 0. - Entnimm
C. EntdeckeAundD. Warteschlange:A, D. Beide erhalten Distanz1und VorgängerC. - Entnimm
A. EntdeckeB;Cist bereits markiert. Warteschlange:D, B. FürBgiltd[B] = 2undπ[B] = A. - Entnimm
D. Die SelbstschleifeD → Dwird ignoriert, weilDbereits markiert ist. Warteschlange:B. - Entnimm
B.Cist bereits markiert. Danach ist die Warteschlange leer.
Die Besuchsreihenfolge lautet C, A, D, B. Die Ebenen sind:
| Ebene | Knoten |
|---|---|
| 0 | C |
| 1 | A, D |
| 2 | B |
Wie findet BFS einen kürzesten Weg?
In einem ungewichteten Graphen zählt jede Kante als ein Schritt. Dasselbe gilt für die Wegeauswahl, wenn alle Kanten dasselbe positive Gewicht besitzen. Dann ist die BFS-Ebene eines Knotens genau seine kleinste erreichbare Kantenzahl vom Start.
Beim ersten Entdecken von v speichert BFS:
- die Distanz
d[v] = d[u] + 1; - den Vorgänger
π[v] = u.
Um einen Weg zu rekonstruieren, folgst du den Vorgängern vom Ziel rückwärts bis zum Start. Anschließend kehrst du die Reihenfolge um.
Im Beispielgraphen gilt π[B] = A und π[A] = C. Rückwärts entsteht B ← A ← C. Umgekehrt gelesen lautet ein kürzester Weg C → A → B. Er besitzt zwei Kanten.
Zu D führt der Weg C → D mit einer Kante.
Mehrere gleich kurze Wege können existieren. Die Reihenfolge der Nachbarn bestimmt dann, welcher Vorgänger zuerst gespeichert und welcher dieser Wege rekonstruiert wird.
Wann ist BFS nicht das passende Wege-Verfahren?
BFS minimiert die Anzahl der Kanten. Bei unterschiedlichen Kantengewichten muss der Weg mit den wenigsten Kanten nicht die geringsten Kosten haben.
Eine direkte Kante S → Z habe Kosten 7. Der Weg S → A → Z bestehe aus zwei Kanten mit Kosten 2 und 2. BFS bevorzugt nach Kantenzahl die direkte Verbindung. Der längere Weg kostet jedoch nur 2 + 2 = 4 und ist damit günstiger.
Für verschieden gewichtete Kanten brauchst du ein Verfahren, das die bisherigen Pfadkosten berücksichtigt. Eine gewöhnliche FIFO-Warteschlange reicht dafür nicht aus.
BFS besucht außerdem nur Knoten, die vom Start aus erreichbar sind. Bei einem gerichteten Graphen kann X von Y aus erreichbar sein, ohne dass auch Y von X aus erreichbar ist.
Was kosten Breitensuche und Zusammenhangstest?
Bei einer Adjazenzliste wird jeder erreichbare Knoten höchstens einmal verarbeitet. Seine ausgehenden Kanten werden einmal untersucht. Für einen vollständig betrachteten endlichen Graphen ergibt sich deshalb die Laufzeit
$$O(|V| + |E|)$$
Dabei bezeichnet |V| die Anzahl der Knoten und |E| die Anzahl der Kanten. Diese Laufzeitaussage bezieht sich auf eine Adjazenzlistendarstellung.
Markierungen, Distanzen, Vorgänger und Warteschlange benötigen zusätzlich bis zu
$$O(|V|)$$
Speicher. Bei sehr breiten Suchräumen können viele Knoten gleichzeitig in der Warteschlange liegen.
BFS eignet sich auch für einen Zusammenhangstest in einem ungerichteten Graphen:
- Starte bei einem beliebigen Knoten.
- Führe BFS vollständig aus.
- Prüfe, ob alle Knoten markiert wurden.
Sind alle Knoten erreicht, ist der Graph zusammenhängend. Bleiben unmarkierte Knoten übrig, liegen sie in anderen Zusammenhangskomponenten.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Breitensuche
- ordnet erreichbare Knoten in Schichten
- steuert die Bearbeitung mit einer FIFO-Warteschlange
- markiert Knoten sofort beim Entdecken
- speichert Distanzen und Vorgänger
- findet kürzeste Wege bei gleichen positiven Kantengewichten
- prüft die Erreichbarkeit vom Start
- benötigt mit Adjazenzlisten `O(|V| + |E|)` Zeit
Abschluss-Check
Du beherrschst die Breitensuche, wenn du Warteschlange, Markierungen, Ebenen und Vorgänger für einen kleinen Graphen selbst dokumentieren und die Voraussetzung für einen kürzesten Weg begründen kannst.