Motivazione

La DFS esplora un grafo scegliendo un percorso e seguendolo fin dove possibile, quindi tornando indietro fino all’ultimo vertice con un vicino non esplorato.

Perché imparare la DFS?

• Fondamentale: è alla base del rilevamento dei cicli, dell’ordinamento topologico, delle componenti connesse e di molti altri algoritmi.
• Semplice ed economica: richiede un tempo O(V + E) usando uno stack (o la ricorsione) e un marcatore di visita.
• Versatile: la stessa visita risponde a domande come «questi due vertici sono connessi?» e «quante parti separate ha il grafo?»

Per mantenere prevedibili i risultati, visitiamo sempre i vicini di un vertice in ordine crescente.