Parcours en profondeur DFS
Un parcours de graphe qui descend aussi loin que possible avant de revenir en arrière — implémenté avec une pile (ou par récursion).
Trois couleurs pour détecter les cycles : blanc (non vu), gris (en cours, sur la pile de récursion), noir (terminé). Une arête qui mène d'un sommet gris à un sommet gris = un cycle. Indispensable pour le tri topologique, la détection de connexité (Tarjan) ou la génération de labyrinthes.
Complexité en temps O(V+E) (sommets + arêtes). Espace dans le pire cas O(V) (récursion profonde). Concurrent : le BFS (parcours en largeur — une file FIFO au lieu d'une pile, il trouve le plus court chemin non pondéré). Pour les graphes profonds, préférer la version itérative afin d'éviter le dépassement de pile.