Graphalgorithmen

Breitensuche

Beispiel

Start

Ziel

Acht Kreuzungen, die Gewichte sind Fahrzeiten in Minuten. Der schnellste Weg von A nach H ist nicht der, der auf der Karte am geradesten aussieht.

Ungerichteter Graph · 8 Knoten · 12 Kanten

Schritt 1 von 42

Tempo

← → Schritt, Leertaste Abspielen

Vorhersagen üben: raten, welcher Knoten als Nächstes drankommt

Start

Start bei A

Die Breitensuche erkundet den Graphen in Wellen: erst alle Nachbarn von A, dann deren Nachbarn und so weiter. d[v] zählt, wie viele Kanten ein Knoten v vom Start entfernt ist, vor[v] merkt sich den Knoten, von dem aus v entdeckt wurde. Zu Beginn kennt die Suche nur A mit d[A] = 0, und A steht allein in der Warteschlange. Die Nachbarn eines Knotens kommen in alphabetischer Reihenfolge an die Reihe.

Start bei A

Warteschlange Q

Vorne wird entnommen, hinten angefügt.

Werte der Knoten

Knoten	Zustand	d	vor
A	wartet	0	–
B	unbekannt	∞	–
C	unbekannt	∞	–
D	unbekannt	∞	–
E	unbekannt	∞	–
F	unbekannt	∞	–
G	unbekannt	∞	–
H	unbekannt	∞	–

d: Abstand in Kanten · vor: Vorgänger

Pseudocoden = 8, m = 12

d[v] ← ∞, vor[v] ← – für alle v; d[s] ← 0; Q ← [s]
solange Q nicht leer ist:
u ← vorderster Knoten aus Q (entfernen)
für jeden Nachbarn v von u:
wenn d[v] = ∞ (v noch unentdeckt):
d[v] ← d[u] + 1, vor[v] ← u, v hinten an Q
u ist abgeschlossen

Eckdaten

Aufwand wächst wie: n + m; n Knoten, m Kanten
Graph: gerichtet oder ungerichtet
Gewichte: ohne Bedeutung; Es zählt nur, welche Knoten verbunden sind.
Start und Ziel: Start nötig, Ziel freiwillig; Mit einem Ziel wird am Ende der Weg dorthin eingezeichnet.

Die Idee

Die Breitensuche breitet sich aus wie eine Welle von einem Stein im Wasser. Erst werden alle Knoten erreicht, die eine Kante entfernt sind, dann alle, die zwei Kanten entfernt sind, und so weiter. Dafür reihen sich neu entdeckte Knoten hinten in einer Warteschlange ein; bearbeitet wird immer, wer vorne steht.

Wie der Aufwand zustande kommt

Jeder Knoten wird einmal entnommen und jede Kante ein- oder zweimal angesehen: Die Arbeit wächst wie n + m.

Mehr zu Breitensuche

Grundbegriffe