La ricerca in profondità (DFS) in Python
In questa lezione percorrerai un grafo con la ricerca in profondità, implementata con una funzione ricorsiva.
Introduzione
Il problema
Trovare l'uscita da un labirinto, controllare se un grafo ha un ciclo o ordinare compiti che dipendono l'uno dall'altro richiedono di seguire un percorso fin dove arriva prima di provarne un altro. Questa è la ricerca in profondità.
Immaginalo così
La ricerca in profondità è il modo in cui esplori una grotta con un gomitolo di filo. Segui un tunnel fin dove arriva. A un vicolo cieco segui il filo indietro fino all'ultimo bivio e provi il tunnel successivo. Segni i tunnel già esplorati così non li percorri mai due volte.
visited.add(node)🧵 Segna questo tunnel come esploratofor neighbor in graph[node]:🔀 Guarda ogni tunnel da quidepth_first(neighbor, visited)⬇️ Scendi nel primo non esploratoreturn order↩️ Vicolo cieco: segui il filo indietroLa ricerca in profondità (DFS) esplora un grafo seguendo un ramo il più in profondità possibile prima di tornare indietro, di solito con la ricorsione o una pila.
Punti chiave
visited.add(node)segna il nodo, così i cicli non causano una ricorsione infinita.for neighbor in graph[node]:guarda ogni vicino a turno.order.extend(depth_first(neighbor, visited))esplora tutto il ramo sotto un vicino prima del successivo.- Il risultato visita D prima di C, perché il ramo di B viene finito prima.
Quando si usa?
- Trovare un percorso qualsiasi, risolvere labirinti e rompicapi con il backtracking.
- Trovare cicli e ordinare compiti con dipendenze (ordinamento topologico).
- Esplorare tutte le parti connesse di un grafo.
Quando non serve
- Ti serve il percorso più breve: la ricerca in profondità può trovare prima un percorso lungo; usa la ricerca in ampiezza.
- Grafi molto profondi: la ricorsione può raggiungere il limite di Python; usa una pila esplicita.
Visualizzatore di La ricerca in profondità (DFS) in Python
O(V + E)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
Risultato dell'esecuzione
['A', 'B', 'D', 'C', 'E']
Spiegazione del codice
L'insieme visited registra i vertici già visitati per evitare ripetizioni e cicli infiniti quando il grafo ha cicli. Ogni chiamata ricorsiva scende in un vicino non ancora visitato, quindi il programma visita A, B, D e solo dopo torna indietro a visitare C ed E. Lo stack delle chiamate fa da pila dell'algoritmo, e la complessità è O(V + E).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Usare un argomento predefinito mutabile
visited=set() verrebbe condiviso tra chiamate separate.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Count Islands Count groups of connected land cells in a grid. Media
- Componenti Fortemente Connesse Conta i gruppi di nodi che possono raggiungersi a vicenda. Difficile
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Difficile