Anwendungen der Breitensuche
Die Breitensuche ist sehr effizient, die Laufzeit ist linear in |E| + |K|. Das Verfahren hat zahlreiche Anwendungen. Wir besprechen einige davon.
Berechnung der Abstandsfunktion
Sei G = (E, K) ein Graph. Dann können wir die Abstandsfunktion d des Graphen berechnen, indem wir BFS nacheinander für jedes a ∈ E als Startecke durchführen. Bei jedem Durchlauf werden die Abstände von der Startecke zu allen anderen Ecken des Graphen berechnet (mit d(a, b) = ∞ genau dann, wenn die Ecke b bei Start in a nicht gefunden wird).
Eine einzige Durchführung von BFS reicht in der Regel nicht. Aus dem Suchbaum für die Startecke a lassen sich Wege zwischen zwei beliebigen Ecken b und c des Suchbaums ablesen, aber diese Wege sind nicht unbedingt kürzeste Wege in G, falls b und c von der Startecke verschieden sind.
Beispiel
Seien G und der BFS-Suchbaum G′ wie im vorangehenden Beispiel. Der Suchbaum berechnet die Abstände d(1, b) für alle b ∈ E. Für die Ecken 7 und 9 liefert der Suchbaum den Weg 7, 6, 3, 10, 9 der Länge 4 in G′. In G gilt aber d(7, 9) = 1, da die beiden Ecken dort benachbart sind.
Jeder Suchbaum liefert aber obere Schranken für die Abstandsfunktion (im Beispiel d(7, 9) ≤ 4). Zudem gilt d(b, c) = ∞ für alle Ecken b eines Suchbaums mit Start bei a, falls c nicht gefunden wird.
Test auf Kreiskante/Brücke, Konstruktion von Kreisen
Sei G = (E, K) ein Graph, und sei ab ∈ K. Sei G′ der Teilgraph von G, der durch Streichen der Kante ab entsteht. Wir konstruieren mit BFS für die Startecke a einen aufspannenden Baum der Zusammenhangskomponente von a in G′. Wird dabei die Ecke b gefunden, so ist ab eine Kreiskante in G, und der durch BFS gefundene Weg von a nach b in G′ liefert durch Anfügen von a einen Kreis in G mit ab als Kante. Andernfalls ist ab keine Kreiskante von G und damit eine Brücke in G.
Beispiel
Sei G = (E, K) mit E = { 1, …, 6 } und K = { 12, 23, 24, 25, 36, 56 }.
Wir betrachten die Kante 23, entfernen sie aus G und führen die Breitensuche im reduzierten Graphen für die Startecke 2 durch. Dies liefert die Stufen
| Stufe 0 | S0 = { 2 } |
| Stufe 1 | S1 = { 1, 4, 5 } |
| Stufe 2 | S2 = { 6 } |
| Stufe 3 | S3 = { 3 } |
Da die Ecke 3 gefunden wird, ist 23 eine Kreiskante von G. Der Suchbaum liefert den Kreis 2, 5, 6, 3, 2.
Eine weitere Anwendung ist:
Test auf bipartit, Konstruktion einer Bipartition
Sei G = (E, K) ein Graph, und sei a ∈ E. Wir führen BFS für die Startecke a durch und färben die Ecken des Suchbaums Stufe für Stufe abwechselnd mit zwei Farben. Nun prüfen wir für jede nicht im Suchbaum enthaltene Kante von G, ob beide Ecken der Kante gleichfarbig sind. Ist dies für eine Kante bc der Fall, so ist die Zusammenhangskomponente von a nicht bipartit (und der Suchbaum liefert einen Kreis ungerader Länge durch bc im Graphen G). Andernfalls ist die Zusammenhangskomponente von a bipartit mit den durch die beiden Farben definieren Eckenmengen.
Beispiel
Sei G = (E, K) mit E = { 1, …, 7 } und
K = { 12, 16, 23, 27, 36, 34, 45, 47, 56 }.
BFS mit der Startecke 1 liefert die grün-gelb-Stufenfärbung
| Stufe 0 | S0 = { 1 } | grün |
| Stufe 1 | S1 = { 2, 6 } | gelb |
| Stufe 2 | S2 = { 3, 5, 7 } | grün |
| Stufe 3 | S3 = { 4 } | gelb |
die ein Kandidat für eine Bipartition ist.
Die von BFS besuchten Kanten (im Diagramm wieder rot gezeichnet) verbinden nach Konstruktion verschiedenfarbige Ecken. Aber auch die nicht besuchten Kanten 36, 45 und 47 (blau gezeichnet) verbinden verschiedenfarbige Ecken. Damit ist der Graph bipartit durch die Färbung, d. h. durch
E1 = { 1, 3, 5, 7 }, E2 = { 2, 4, 6 }.
Mit dem BFS-Verfahren sind alle algorithmischen Fragen, die wir zu Beginn des Kapitels formuliert haben, beantwortet. Darüber hinaus haben wir einen effizienten Bipartitionstest gefunden, der im positiven Fall auch eine Zerlegung der Eckenmenge in zwei Teile liefert. Als Kontrast erwähnen wir, dass ein Test auf 3-partit bereits NP-vollständig ist.