Algoritmi Python

La ricerca in profondità (DFS) in Python

In questa lezione percorrerai un grafo con la ricerca in profondità, implementata con una funzione ricorsiva.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dall'esplorare una grotta al codice
visited.add(node)🧵 Segna questo tunnel come esplorato
for neighbor in graph[node]:🔀 Guarda ogni tunnel da qui
depth_first(neighbor, visited)⬇️ Scendi nel primo non esplorato
return order↩️ Vicolo cieco: segui il filo indietro
Prima vai in profondità, poi torna indietro e prova il ramo successivo.
In una frase

La 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

  1. visited.add(node) segna il nodo, così i cicli non causano una ricorsione infinita.
  2. for neighbor in graph[node]: guarda ogni vicino a turno.
  3. order.extend(depth_first(neighbor, visited)) esplora tutto il ramo sotto un vicino prima del successivo.
  4. 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

Esegui codice →
main.py
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"))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Usare un argomento predefinito mutabile

visited=set() verrebbe condiviso tra chiamate separate.

Problema
def depth_first(node, visited=set()):
Correzione
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.

Tutte le sfide