DFS (Tiefensuche)
Graphtraversierung, die so tief wie möglich vordringt, bevor sie zurückgeht — implementiert mit einem Stack (oder Rekursion).
Drei Farben für die Zykluserkennung: weiß (unbesucht), grau (in Bearbeitung, liegt gerade auf dem Rekursions-Stack), schwarz (fertig). Eine Kante von Grau zu Grau bedeutet einen Zyklus. Das wird für topologische Sortierung, Zusammenhangserkennung (Tarjans Algorithmus) und Labyrinth-Generierung gebraucht.
Zeitkomplexität O(V+E), im schlimmsten Fall Platzbedarf O(V) durch tiefe Rekursion. Die Konkurrenz heißt BFS (FIFO statt Stack, findet den kürzesten ungewichteten Weg). Für tiefe Graphen empfiehlt sich die iterative Variante, um einen Stack Overflow zu vermeiden.