Die Tiefensuche

Eine Variante der Breitensuche ist die Tiefensuche DFS (depth first search), die wir noch kurz diskutieren wollen. Bei dieser Form der Suche eines aufspannenden Baumes bilden wir den Suchbaum nicht stufenweise, sondern wir verfolgen einen Suchpfad so weit wie möglich. Ist ein solcher Pfad zu Ende, weil wir keinen neuen Nachbarn mehr finden, fallen wir auf dem Pfad einen Schritt zurück und starten die Pfadsuche neu. Genauer lautet das Verfahren:

Tiefensuche (DFS)

Sei G = (E, K) ein Graph, und sei e₀  ∈  E eine Startecke. Wir konstruieren rekursiv Ecken e₁, e₂, … und Kanten k₁, k₂, … des Graphen wie folgt:

Sei m ≥ 0, und seien Ecken e₀, …, e_m und Kanten k₁, …, k_m konstruiert (eine Kante k₀ existiert nicht). Im Fall der Existenz sei e_m + 1 eine bislang unbesuchte Nachbarecke von e_m und k_m = e_me_m + 1 (Fortsetzung des aktuellen Suchpfades). Gibt es keine solche Ecke, so führen wir die Suche nach einer neuen Nachbarecke schrittweise für die Ecken durch, die im konstruierten Baum auf dem Weg von e_m nach e₀ liegen (Zurückgehen auf dem Suchpfad). Finden wir dabei einen neuen Nachbarn e einer Ecke e_i, so setzen wir e_m + 1 = e und k_m = e_ie. Andernfalls stoppen wir mit

G′ = (E′, K′) = ({ e₀, …, e_m }, { k₁, …, k_m }).

Wir können das Verfahren wieder deterministisch gestalten, indem wir dem Prinzip der kleinsten Wahl folgen.

Die Tiefensuche produziert wie die Breitensuche einen aufspannenden Baum der Zusammenhangskomponente der Startecke, und sie kann für einen Kreiskanten-Brücken-Test verwendet werden. Für eine Abstandsmessung und einen Bipartitionstest ist DFS dagegen nicht geeignet. Die Laufzeit entspricht der Laufzeit der Breitensuche.

Beispiele

(1)

Sei wie oben 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 von DFS für die Startecke 1 liefert:

Eckenfolge: 1, 2, 3, 4, 6, 5, 7, 8, 9, 10

Kantenfolge: 12, 23, 34, 46, 65, 67, 78, 89, 9-10.

Ein Zurückgehen auf dem Suchpfad findet einmal bei der Kante 67 statt: Ist 1, 2, 3, 4, 6, 5 konstruiert, so hat die 5 keine unbesuchten Nachbarn. Wir fallen auf die 6 zurück und finden den neuen Nachbarn 7. Danach werden die Ecken 8, 9, 10 ohne Rückfall durchlaufen.

Verlauf des DFS-Verfahrens für die Startecke 1 (oben) und der von links nach rechts gestufte Suchbaum (unten)

(2)

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

K = { 12, 13, 24, 35, 36, 47, 48 }.

Der Graph G ist bereits ein Baum. Die Breitensuche mit Startecke 1 reproduziert die Folge der Ecken mit den Stufen

{ 1 }, { 2, 3 }, { 4, 5, 6 }, { 7, 8 }.

Die Tiefensuche mit Start bei 1 liefert dagegen:

Eckenfolge: 1, 2, 4, 7, 8, 3, 5, 6

Kantenfolge: 12, 24, 47, 48, 13, 35, 36

Hier findet ein Rückfall nach Besuch der Ecken 7, 8 und 5 statt. Der Rückfall nach Besuch der 8 geht bis zur Startecke 1 zurück.