DFS
Algoritmo di visita di un grafo: si scende il più possibile lungo ogni ramo prima di tornare indietro. Si implementa in modo ricorsivo o con una pila.
Usi: ordinamento topologico, rilevamento di cicli, componenti connesse, risoluzione di labirinti, passate del compilatore. Gli algoritmi di Tarjan per le componenti fortemente connesse e per i ponti si basano sulla DFS. A differenza della BFS usa meno memoria (O(d) in profondità), ma non trova i cammini minimi. La versione iterativa con pila evita lo stack overflow sui grafi molto profondi. Anche git log percorre il DAG dei commit con una DFS.