Die Tiefensuche (englisch Depth-First Search, kurz DFS) ist ein Algorithmus, der einen Graphen oder Baum systematisch durchläuft, indem er einem Pfad möglichst weit in die Tiefe folgt und erst dann zurückgeht (backtrackt), wenn keine unbesuchten Nachbarn mehr existieren. Sie zählt neben der Breitensuche zu den beiden grundlegenden Suchstrategien der Graphen- und Baum-Verarbeitung.
Wie funktioniert die Tiefensuche?
Der Algorithmus startet an einem Startknoten und folgt einer Kante so lange wie möglich: Er besucht den ersten Nachbarn, dann dessen ersten Nachbarn, dann wieder dessen ersten Nachbarn – bis er an einem Knoten ankommt, der keine unbesuchten Nachbarn mehr hat. Dort kehrt er zur letzten Verzweigung zurück und probiert den nächsten Pfad. Diese Strategie heißt Depth-First, weil die Suche zuerst die Tiefe ausschöpft, bevor sie die Breite erkundet.
Die Tiefensuche lässt sich auf zwei Arten umsetzen:
- Rekursiv: Die Funktion ruft sich für jeden unbesuchten Nachbarn selbst auf – elegant und kompakt, aber bei sehr tiefen Graphen kann der Aufrufstapel wachsen.
- Iterativ mit Stack: Ein expliziter Stack übernimmt die Rolle des Aufrufstapels; der Algorithmus legt Knoten auf den Stack und nimmt sie nach dem LIFO-Prinzip (Last In, First Out) wieder herunter.
Wichtig ist, besuchte Knoten zu markieren: In Graphen mit Zyklen käme der Algorithmus sonst in eine Endlosschleife, weil er immer wieder zu bereits gesehenen Knoten zurückkehren würde.
Laufzeit und Speicher
Die Tiefensuche besucht jeden Knoten und jede Kante höchstens einmal. Bei einem Graphen mit V Knoten und E Kanten beträgt die Laufzeit daher O(V + E) – genauso wie bei der Breitensuche. Der Speicherbedarf ist dagegen geringer: Der Algorithmus merkt sich nur den aktuellen Pfad und dessen Verzweigungen, benötigt also im günstigsten Fall nur O(V) Speicher für den Stack.
Typische Anwendungen
- Labyrinthe und Puzzles: DFS findet einen Weg durch ein Labyrinth, indem sie Pfad für Pfad ausprobiert und bei Sackgassen zurückgeht.
- Topologische Sortierung: Die Nachordnung der Tiefensuche liefert direkt eine Reihenfolge, in der Abhängigkeiten erfüllt sind – Grundlage des Artikels Topologische Sortierung.
- Zyklenerkennung: Beobachtet man während der Suche Kanten zu Knoten, die sich bereits im aktuellen Pfad befinden, hat der Graph einen Zyklus.
- Zusammenhängende Komponenten: Ein Durchlauf erreicht genau alle Knoten einer Zusammenhangskomponente; man findet sie, indem man für jeden noch unbesuchten Knoten einen neuen DFS-Lauf startet.
- Spielbäume und Backtracking: Viele Such- und Lösungsverfahren nutzen DFS, etwa das Backtracking bei Sudoku oder Damenproblem.
Abgrenzung zur Breitensuche
Der entscheidende Unterschied ist die Reihenfolge: Die Tiefensuche geht zuerst in die Tiefe, die Breitensuche erkundet dagegen Ebene für Ebene über eine Warteschlange. Wer den kürzesten Weg in einem ungewichteten Graphen sucht, nimmt die Breitensuche – die Tiefensuche findet einen beliebigen Weg, aber nicht unbedingt den kürzesten. Weitere Details zu den Eigenschaften finden sich im Artikel Traversierung.
Verwandte Grundlagen: Graph-Datenstruktur | Baum-Datenstruktur | Rekursion | Stack | Big-O-Notation