DFS — algoritmo di ricerca in profondità spiegato

La ricerca in profondità, o DFS, è un algoritmo per esplorare un albero o un grafo seguendo un percorso il più lontano possibile prima di fare backtracking. In parole semplici: DFS continua ad andare più in profondità finché non si blocca, poi torna all’ultimo punto in cui è disponibile un altro ramo.

Se devi ricordare una sola idea, ricorda questa: DFS significa "vai in profondità, poi fai backtracking".

Cosa fa la ricerca in profondità

DFS può essere usato sugli alberi e sui grafi generali. Partendo da un nodo, si sposta ripetutamente verso un vicino non visitato. Quando raggiunge un nodo che non ha più vicini non visitati, torna al nodo precedente e continua da lì.

Questo backtracking è il comportamento che la definisce. Nelle implementazioni ricorsive, lo stack delle chiamate lo gestisce automaticamente. Nelle implementazioni iterative, uno stack esplicito svolge lo stesso ruolo.

Perché l’ordine di DFS può cambiare

DFS non produce un unico ordine di visita universale. L’ordine esatto dipende dall’ordine in cui vengono considerati i vicini.

Per esempio, se un nodo ha come vicini $B$ e $C$, visitare prima $B$ può dare un ordine DFS diverso rispetto a visitare prima $C$. In entrambi i casi la ricerca è comunque DFS, perché la regola è la stessa: continuare ad andare in profondità prima di esplorare un ramo fratello.

Esempio di DFS su un piccolo grafo

Supponiamo che il grafo abbia queste connessioni:

• $A$ è collegato a $B$ e $C$
• $B$ è collegato a $D$ e $E$
• $C$ è collegato a $F$

Supponiamo di esaminare sempre i vicini da sinistra a destra e di partire da $A$.

DFS procede così:

1. Visita $A$
2. Vai a $B$
3. Vai a $D$
4. $D$ non ha vicini non visitati, quindi fai backtracking fino a $B$
5. Da $B$, vai a $E$
6. $E$ è completato, quindi fai backtracking fino a $B$, poi fino a $A$
7. Da $A$, vai a $C$
8. Da $C$, vai a $F$

Quindi un possibile ordine di visita DFS è:

$$A, B, D, E, C, F$$

L’idea chiave è che DFS completa il lato $A \to B$ prima di iniziare il lato $A \to C$. Se cambiassi l’ordine dei vicini, potrebbe cambiare anche l’ordine di visita.

Perché il backtracking usa uno stack

DFS ha sempre bisogno di un modo per ricordare dove tornare dopo aver raggiunto un vicolo cieco. Per questo gli stack compaiono naturalmente in DFS.

Nella DFS ricorsiva, ogni chiamata di funzione resta in attesa mentre la ricerca va più in profondità, e il programma ritorna in ordine inverso quando fa backtracking. Nella DFS iterativa, inserisci i nodi in uno stack e li estrai quando è il momento di continuare dal punto incompleto più recente.

Complessità temporale e spaziale di DFS

Se il grafo è memorizzato come lista di adiacenza e ogni vertice viene segnato la prima volta che viene visitato, DFS richiede

$$O(V + E)$$

tempo per la parte raggiungibile del grafo, dove $V$ è il numero di vertici ed $E$ è il numero di archi.

Lo spazio aggiuntivo è tipicamente

$$O(V)$$

perché la struttura dei visitati e lo stack di ricorsione o lo stack esplicito possono entrambi crescere con il numero di vertici.

Errori comuni in DFS

Dimenticare di segnare i nodi visitati

In un grafo generale, dimenticare il controllo dei visitati può far entrare DFS in un ciclo all’infinito. Anche in un albero memorizzato come grafo non orientato, devi comunque evitare di tornare subito al nodo padre, a meno che il tuo codice gestisca esplicitamente quel caso.

Supporre che DFS trovi il cammino più breve

DFS può trovare un cammino, ma in generale non garantisce il cammino più breve in un grafo non pesato. Se l’obiettivo è il cammino più breve e tutti gli archi hanno lo stesso peso, BFS è di solito il punto di partenza giusto.

Considerare l’ordine DFS come unico

L’ordine dipende dall’ordine dei vicini. Se quell’ordine cambia, può cambiare anche l’ordine di attraversamento.

Quando si usa la ricerca in profondità

DFS è utile quando vuoi esplorare la struttura invece di cercare prima solo la distanza minima. Gli usi comuni includono:

• verificare se un nodo è raggiungibile
• trovare le componenti connesse
• rilevare cicli in alcune configurazioni di grafi
• attraversare alberi
• risolvere problemi di backtracking come labirinti o ricerca di soluzioni in puzzle

Il motivo principale per cui compare così spesso è che "vai in profondità, poi fai backtracking" si adatta a molte strutture di problemi ricorsivi.

DFS vs BFS: la differenza pratica

DFS scende prima lungo un ramo. BFS esplora tutti i nodi a una certa distanza prima di passare alla distanza successiva.

Se ti interessa un’esplorazione completa o una struttura ricorsiva, DFS è spesso naturale. Se ti interessa il cammino più breve in un grafo non pesato, BFS è spesso la scelta iniziale più sicura.

Prova un attraversamento simile

Disegna un piccolo grafo con sei nodi e scegli un ordine fisso dei vicini. Esegui DFS a mano e annota esattamente quando vai avanti e quando fai backtracking. Se il tuo ordine cambia dopo aver riordinato i vicini, non è un errore. Fa parte del funzionamento di DFS.