DFS (ricerca in profondità)
Visita di un grafo che scende il più possibile in profondità prima di tornare indietro (backtracking), implementata con una pila o con la ricorsione.
Per rilevare i cicli si usano tre colori: bianco (non visitato), grigio (in corso, presente sulla pila di ricorsione), nero (completato). Un arco verso un nodo grigio indica un ciclo. È alla base dell'ordinamento topologico, del rilevamento della connettività (Tarjan) e della generazione di labirinti.
Complessità temporale O(V+E); nel caso peggiore lo spazio è O(V) (ricorsione profonda). L'alternativa è la BFS (coda FIFO invece della pila, trova il cammino più breve nei grafi non pesati). Per i grafi molto profondi si consiglia la DFS iterativa, per evitare lo stack overflow.