DFS (Depth-First Search)
Graafdoorloop die zo diep mogelijk gaat voordat hij teruggaat (backtracking) — geïmplementeerd met een stack (of recursie).
Drie kleuren voor cyclusdetectie: wit (nog niet gezien), grijs (in behandeling, op de recursiestack) en zwart (klaar). Een kant naar een grijze knoop = een cyclus. Nodig voor topologisch sorteren, connectiviteitsdetectie (Tarjan) en het genereren van doolhoven.
Tijdscomplexiteit O(V+E). Ruimte in het slechtste geval O(V) (diepe recursie). Tegenhanger: BFS (FIFO in plaats van stack, vindt het kortste ongewogen pad). Voor diepe grafen is iteratieve DFS aan te raden om stack overflow te vermijden.