Aufspannende Bäume und Breitensuche

 Bäume sind äußerst nützliche Hilfsmittel zur algorithmischen Analyse von beliebigen Graphen. Entscheidend hierzu ist folgender Begriff:

Definition (aufspannender Baum)

Sei G = (E, K) ein zusammenhängender Graph. Ein Teilgraph G′ = (E′, K′) von G, heißt ein aufspannender Baum von G, falls gilt:

(a)

E′ = E.

(b)

G′ ist ein Baum.

 Ein aufspannender Baum G′ eines Graphen G besitzt also alle Ecken und gewisse (möglicherweise alle) Kanten von G. Als Baum ist G′ wie G zusammenhängend. Wir können einen aufspannenden Baum als eine so weit wie möglich reduzierte Version des ursprünglichen Graphen ansehen. Diese Sicht verwenden wir im Beweis des folgenden Existenzsatzes:

Satz (Existenz eines aufspannenden Baumes)

Sei G = (E, K) ein zusammenhängender Graph. Dann existiert ein aufspannender Baum von G.

Beweis

Wir entfernen aus G solange wie möglich Kanten, die auf einem Kreis liegen. Da der Zusammenhang durch das Streichen einer Kreiskante gewahrt bleibt, erreichen wir nach endlich vielen Schritten einen zusammenhängenden kreisfreien Graphen G′ der Form (E, K′) mit K′ ⊆ K. Dieser Graph ist ein aufspannender Baum von G.

Beispiel

Der rot markierte Teilgraph des folgenden Graphen ist ein aufspannender Baum. Er entsteht durch wiederholtes Entfernen von Kreiskanten.

ema21-AbbID2-5-9

Die Breitensuche

 Aus algorithmischer Sicht benötigt die Konstruktion des aufspannenden Baumes G′ des obigen Beweises einen Test auf „Ist ab Kante eines Kreises?“, der unnötige Rechenzeit verschwendet. Wesentlich effizienter ist ein anderes Verfahren, das einen aufspannenden Baum stufenweise konstruiert. Es ist nützlich, dieses Verfahren für beliebige Graphen zu formulieren und den Zusammenhang nicht vorauszusetzen.

Breitensuche (BFS)

Sei G = (E, K) ein Graph, und sei a  ∈  E eine Startecke. Wir konstruieren Bäume Gi = (Ei, Ki) wie folgt.

Zunächst sei G0 = ({ a }, ∅) der Graph, der nur aus der Startecke besteht.

Ist Gi konstruiert, so seien e1, … ek die unbesuchten Nachbarn der bereits besuchten Ecken, d. h. die Ecken in E − Ei, die mit mindestens einer Ecke in Ei benachbart sind (sog. angrenzende Ecken). Wir stoppen mit Ergebnis Gi, falls es keine solchen Ecken gibt. Andernfalls setzen wir

Ei + 1  =  Ei ∪ { e1, …, ek }.

Nun fügen wir für jede Ecke e1, …, ek eine Kante zu Ki hinzu, die ei mit einer Ecke in Ei verbindet. Dies definiert Ki + 1 und damit den Graphen

Gi + 1  =  (Ei + 1, Ki + 1).

 Die Abkürzung BFS steht für „breadth first search“.

 Wir nennen einen durch BFS erzeugten Baum auch einen Suchbaum. Weiter sagen wir, dass eine Ecke b  ∈  E auf der Stufe i gefunden wird, wenn b  ∈  Ei − Ei − 1 gilt (mit E−1 = ∅). Wird b auf der Stufe i gefunden, so liefert der Suchbaum einen Weg der Länge i von der Startecke a nach b, sodass d(a, b) ≤ i. Wir werden gleich zeigen, dass dieser Weg ein kürzester Weg ist, d. h. es gilt d(a, b) = i.

Bemerkung

Einen deterministischen Verlauf erhalten wir, indem wir

(a)

die Ecken in der Form 1, …, n durchzählen,

(b)

die neuen Ecken in der Form e1 < … < ek anordnen,

(c)

neue Kanten bei stets mit der kleinstmöglichen Ecke b  ∈  Ei zu Ki hinzufügen.

 Allgemein können wir eine deterministische Version für jeden Algorithmus erhalten, indem wir folgendes Prinzip beachten (das wir schon beim Algorithmus von Hierholzer angewendet haben):

Prinzip der kleinsten Wahl

Wähle den kleinsten Kandidaten, wo immer möglich.

Beispiel

Sei G = (E, K) mit E = { 1, …, 10 } und

K  =  { 12, 13, 14, 23, 24, 34, 35, 36, 3-10, 46, 56, 67, 78, 79, 89, 9-10 }.

Die deterministische Version der Breitensuche liefert für die Startecke 1 den Baum G′ = (E, K′) mit

K′  =  { 12, 13, 14, 35, 36, 3-10, 67, 9-10, 78 }.

ema21-AbbID2-5-10

Die Stufenbildung mit Si = Ei − Ei − 1 lautet:

Stufe 0S0  =  { 1 }
Stufe 1S1  =  { 2, 3, 4 }
Stufe 2S2  =  { 5, 6, 10 }
Stufe 3S3  =  { 7, 9 }
Stufe 4S4  =  { 8 }
ema21-AbbID2-5-11

G mit dem BFS-Suchbaum für die Startecke 1, von links nach rechts gestuft

 Die Breitensuche leistet:

Satz (Korrektheit des BFS Algorithmus und Abstandsermittlung)

Der BFS Algorithmus liefert für die Startecke a einen aufspannenden Baum G′ = (E′, K′) der Zusammenhangskomponente der Ecke a. Insbesondere ist G genau dann zusammenhängend, wenn E′ = E. Genauer gilt:

(a)

Ist b  ∈  E und W = a0, …, an ein kürzester Weg von a0 = a nach b = an, so gilt für alle i ≤ n: ai wird auf der Stufe i gefunden.

(b)

Wird eine Ecke b auf der Stufe i gefunden, so gilt d(a, b) = i und der eindeutige Weg von a nach b im Suchbaum ist ein kürzester Weg von a nach b der Länge i.

Beweis

Die Aussage (a) ergibt sich für einen kürzesten Weg W = a0, …, an von a nach b durch Induktion nach i ≤ n. Die restlichen Aussagen folgen aus (a) und der Konstruktion des Suchbaums.