DFS, ricorsione e stack iterativi
Esplorare in profondità evitando i limiti della ricorsione
DFS, ricorsione e stack iterativi è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cosa fa DFS
DFS percorre un cammino il più in profondità possibile, poi torna indietro e prova quello successivo. È come esplorare un labirinto corridoio dopo corridoio. 🧭
DFS e BFS a confronto
BFS si espande per livelli, mentre DFS va prima in profondità. Entrambi visitano tutti i nodi raggiungibili, ma in un ordine molto diverso.
La struttura ricorsiva
La DFS ricorsiva marca un nodo come visited, poi richiama sé stessa su ogni vicino non visitato. Lo stack delle chiamate ricorda dove tornare.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Marcare prima della ricorsione
Impostate visited entrando in un nodo, prima di esplorarne i vicini. Altrimenti i cicli portano DFS in una ricorsione infinita.
Il problema del limite di ricorsione
Python limita la ricorsione a circa 1000 chiamate. Un grafo profondo provoca un RecursionError, che viene segnalato come errore di esecuzione.
Aumentare il limite
Una soluzione rapida consiste nell’aumentare il limite con setrecursionlimit. Impostatelo oltre la profondità massima prevista prima di eseguire DFS.
import sys
sys.setrecursionlimit(300000)Usare invece una versione iterativa
La soluzione più sicura è una DFS iterativa che utilizza uno stack gestito direttamente. Senza profondità delle chiamate, non si verificano errori di ricorsione.
stack = [start]Estrarre dallo stack
A ogni passaggio si estrae l’elemento in cima allo stack. L’ordine LIFO, cioè ultimo a entrare e primo a uscire, mantiene DFS sul cammino più recente.
u = stack.pop()Inserire i vicini
Dopo aver estratto u, si inserisce ogni vicino non visitato nello stack. È necessario marcarli per evitare di inserirli di nuovo.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Il ciclo iterativo completo
Si ripetono le operazioni di estrazione e inserimento finché lo stack contiene nodi. Quando si svuota, tutti i nodi raggiungibili sono stati visitati.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Lo stesso costo di BFS
Come BFS, DFS visita ogni nodo e ogni arco una sola volta, quindi ha complessità O(n + m). La scelta dipende dall’ordine più adatto al problema.
Verifica rapida
La DFS ricorsiva va in errore su un grafo profondo. Perché?
Riepilogo
Si può eseguire DFS in modo ricorsivo o con uno stack proprio, marcando i nodi come visitati all’ingresso e passando alla versione iterativa quando il grafo è profondo. 🎉
Domande Frequenti
La lezione «DFS, ricorsione e stack iterativi» è gratuita?
Sì — il testo completo di «DFS, ricorsione e stack iterativi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «DFS, ricorsione e stack iterativi»?
Esplorare in profondità evitando i limiti della ricorsione Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «DFS, ricorsione e stack iterativi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Liste di adiacenza dall’input
- BFS per i cammini minimi non pesati
- DFS, ricorsione e stack iterativi
- Componenti connesse e flood fill