Tiefensuche

Tiefensuche, im Bereich der Graphentheorie üblicherweise als Depth-First Search (DFS) bezeichnet, ist ein Algorithmus zur Traversierung oder Durchsuchung von Graphen und Bäumen. Von einem Startknoten aus wird so weit wie möglich entlang eines Pfades fortgegangen, bevor neue Verzweigungen durchsucht werden. Im Gegensatz zur Breitensuche erkundet DFS die Tiefe der Struktur vor der Erkundung benachbarter Knoten.

Die Implementierung erfolgt typischerweise rekursiv oder mit einem expliziten Stack. Alle Knoten werden beim ersten Besuch markiert, um Wiederholungen zu verhindern. DFS unterscheidet zwischen gerichteten und ungerichteten Graphen; in beiden Fällen wird jeder Knoten genau einmal entdeckt, aber die Traversal-Reihenfolge hängt von der Adjazenzstruktur ab.

Die Laufzeit beträgt gewöhnlich O(V+E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist. Der räumliche Speicherbedarf liegt im Maximum bei O(V) aufgrund der Rekursionstiefe oder des Stacks. DFS liefert oft eine Tiefen- oder Pre-/Post-Order-Einsortierung der Knoten, was für weitere Algorithmen nützlich ist.

Varianten schließen die depth-limited search ein, die maximale Tiefe begrenzt, sowie iterative deepening, das Wiederholungsdurchläufe mit zunehmender Tiefe kombiniert. Anwendungen finden sich in der Topologischen Sortierung, der Erkennung von Zyklen, der Bestimmung von stark zusammenhängenden Komponenten sowie in der Lösung von Puzzles und Maze-Problemen. In der Praxis wird DFS auch als Vorbereitungsschritt für komplexe Graph-Algorithmen genutzt.

Im Gegensatz zur Breitensuche, die Knoten Ebene für Ebene durchsucht und oft den kürzesten Weg in ungewichteten Graphen liefert, priorisiert DFS die Fortsetzung in der aktuellen Verzweigung. Dadurch kann DFS weniger Speicher benötigen, führt aber oft zu längeren Pfaden oder rendert Pfade nicht optimal.