Depth-First Search in Python: attraversare grafi e alberi

Immagina di esplorare un vasto sistema di grotte. Scegli una galleria e la segui fin dove arriva, sempre più in profondità, finché non incontri un vicolo cieco. Poi torni indietro fino all’ultimo bivio e provi una nuova galleria. Questo metodo di esplorazione in profondità, tornando sui tuoi passi solo quando serve, è molto simile alla depth-first search (DFS), un algoritmo fondamentale per navigare strutture dati come grafi e alberi.

Se ti interessano strutture dati, algoritmi e problem solving, su DataCamp trovi tutto: scopri di più sulle diverse strutture dati e sui migliori algoritmi per esplorarle con il corso Data Structures and Algorithms in Python e il tutorial Data Structures: A Comprehensive Guide With Python Examples.

Che cos’è la Depth-First Search?

La depth-first search (DFS) è un algoritmo usato per attraversare o cercare all’interno di una struttura dati, come un grafo o un albero. L’idea di base della DFS è esplorare una diramazione del grafo o dell’albero il più a fondo possibile prima di tornare indietro per esplorare rami alternativi. Questo approccio contrasta con la breadth-first search, che esplora tutti i nodi al livello di profondità corrente prima di passare al successivo. Puoi leggere della breadth-first search QUI.

Pensa alla depth-first search come a un modo per esplorare un labirinto: scegli un percorso e lo segui finché non arrivi a un vicolo cieco. Una volta raggiunta la fine di quel percorso, torni all’ultimo punto decisionale e provi una strada diversa. Questa esplorazione in profondità rende la DFS un’ottima scelta quando l’obiettivo è esplorare completamente una struttura, soprattutto se ha molti possibili percorsi.

La DFS è particolarmente utile nei problemi in cui hai bisogno di esplorare ogni possibile soluzione.

Alcuni esempi includono:

• Navigazione di alberi decisionali in AI, dove ogni ramo rappresenta una sequenza di scelte e l’obiettivo è valutare tutti i possibili esiti.
• Problemi di pathfinding, come muoversi su una scacchiera o trovare percorsi su una mappa, che richiedono ricerche esaustive.

La DFS garantisce che ogni nodo venga visitato una volta e che l’algoritmo copra l’intero grafo o albero.

Caratteristiche chiave della Depth-First Search in Python

La depth-first search adotta un approccio sistematico per esplorare i nodi e fare backtracking solo quando necessario. Vediamo alcune delle sue caratteristiche principali.

Natura ricorsiva

Alla base, la DFS funziona in modo ricorsivo, cioè risolve il problema richiamando ripetutamente se stessa man mano che esplora più a fondo la struttura. Quando la DFS scende in un ramo, lo esplora il più profondamente possibile prima di risalire per esplorare altri rami. Questo processo di addentrarsi in un percorso e fare backtracking quando non ci sono ulteriori opzioni è gestito in modo ideale tramite la ricorsione. Dai un’occhiata a Understanding Recursive Functions in Python per un approfondimento su cosa sono le funzioni ricorsive e quando sono utili.

Backtracking

Il backtracking è essenziale per la DFS. Quando l’algoritmo raggiunge un nodo che non ha vicini non visitati, torna indietro al nodo precedente e verifica se lì esistono altri vicini non visitati. Se ci sono, li esplora; altrimenti continua a fare backtracking. Questo ciclo di immersione e ritorno prosegue finché tutti i percorsi possibili sono stati coperti o finché non viene soddisfatta una condizione di arresto.

Gestione dei cicli

I grafi possono contenere cicli, cioè percorsi che ritornano su se stessi. Senza le dovute precauzioni, la DFS potrebbe rivisitare all’infinito i nodi in questi cicli. Segnando ogni nodo come visitato la prima volta che viene incontrato, la DFS evita di tornare inutilmente sui propri passi. In questo modo, anche nei grafi ciclici, la DFS resta efficiente ed evita loop infiniti.

Esplorazione completa

Uno dei tratti distintivi della DFS è la capacità di esplorare completamente una struttura. L’algoritmo prosegue finché ogni nodo è stato visitato. Questo è particolarmente utile quando devi assicurarti di non perdere alcuna potenziale soluzione, ad esempio nella risoluzione di puzzle, nell’esplorazione di alberi decisionali o nella navigazione di labirinti.

Implementare la Depth-First Search in Python

Ci sono due modi principali per implementare una depth-first search in Python: ricorsivamente e iterativamente. Ciascun approccio ha vantaggi e compromessi, e la scelta spesso dipende dalla dimensione del grafo e dal problema che stai risolvendo.

Per illustrare entrambi i metodi, creiamo un semplice albero decisionale e usiamo la DFS per attraversarlo. Useremo Python per il nostro esempio. Puoi sempre dare un ripasso alle tue competenze Python con lo skill track Python Programming.

Prendiamo come esempio un albero decisionale binario. Ecco una semplice struttura in cui ogni nodo ha due rami figli:

Definiamo esplicitamente questo albero decisionale in Python come un dizionario.

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}Offerto da

DFS ricorsiva

La DFS è spesso implementata in modo ricorsivo. A ogni nodo, la DFS richiama se stessa sui nodi figli finché non ce ne sono più da visitare, poi fa backtracking. Ecco una funzione DFS ricorsiva per attraversare l’albero.

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')Offerto da

In questa versione ricorsiva, partiamo dal nodo radice A ed esploriamo in profondità ogni ramo prima di tornare indietro per esplorare le alternative. Se eseguiamo questo codice, stamperà il percorso seguito durante l’attraversamento dell’albero:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
OOfferto da

DFS iterativa

Per alberi decisionali molto grandi, il limite di profondità della ricorsione di Python potrebbe causare problemi. In quei casi, possiamo implementare la DFS in modo iterativo, usando uno stack per gestire i nodi da visitare. Ecco come potremmo implementare la DFS iterativa per lo stesso albero decisionale:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')Offerto da

Questo approccio iterativo evita i limiti della profondità di ricorsione gestendo manualmente lo stack, utile per alberi grandi o strutture profonde. L’esecuzione di questo codice produce lo stesso output di sopra.

Quando usare la DFS ricorsiva rispetto a quella iterativa

Sia l’approccio ricorsivo che quello iterativo alla depth-first search sono strumenti preziosi, ma la scelta tra i due dipende dalla struttura del grafo e dalle tue esigenze specifiche. Vediamo più da vicino i punti di forza e i limiti di ciascun approccio.

DFS ricorsiva

In generale preferisco la semplicità ed eleganza della DFS ricorsiva. Questo approccio è intuitivo e pulito.

Pro:

• Semplicità: il codice è compatto e rispecchia bene il problema.
• Leggibilità: più facile da capire, soprattutto per problemi di piccole e medie dimensioni.

Contro:

• Limite di profondità della ricorsione: per grafi grandi, potresti incorrere nel limite di profondità della ricorsione di Python.

La ricorsione è ideale per problemi in cui l’albero o il grafo è relativamente piccolo e rientra comodamente nel limite di ricorsione di Python.

DFS iterativa

Pur essendo leggermente più complessa da scrivere, la DFS iterativa è più flessibile e può gestire problemi più grandi senza preoccuparsi dei limiti di ricorsione. Invece di affidarsi allo stack delle chiamate di Python, la DFS iterativa gestisce esplicitamente i nodi da esplorare tramite uno stack.

Pro:

• Nessun limite di ricorsione: gestire manualmente lo stack evita il limite di profondità della ricorsione di Python.

Contro:

• Più codice: la DFS iterativa richiede più setup e può essere meno intuitiva.
• Leggibilità: il codice è spesso un po’ più verboso e quindi meno immediato da seguire.

L’approccio iterativo è ideale per problemi grandi o complessi in cui la profondità di ricorsione è un problema. È utile anche quando ti serve un maggior controllo sull’attraversamento.

Complessità temporale e spaziale

La DFS è un algoritmo efficiente, ma le sue prestazioni sono influenzate dalla dimensione e dalla struttura del grafo che sta esplorando. Il tempo di esecuzione e la memoria utilizzata dipendono dal numero di nodi visitati e dalle connessioni tra essi.

Usiamo la notazione Big O per parlare di complessità. Per un ripasso sulla notazione Big O, dai un’occhiata alla Big O Notation and Time Complexity Guide: Intuition and Math.

Complessità temporale

La complessità temporale della DFS è O(V + E), dove V è il numero di nodi ed E è il numero di connessioni (dette "archi"). La DFS visita ogni nodo e ogni connessione una volta. Quindi, il tempo totale dipende da quanti nodi e connessioni ci sono.

Complessità spaziale

Lo spazio usato nella DFS dipende da quanti nodi l’algoritmo tiene traccia in un dato momento. Sia la DFS ricorsiva che quella iterativa usano uno stack per tenere traccia dei nodi in esplorazione. Nel caso peggiore, la memoria può contenere tutti i nodi del grafo, portando a una complessità spaziale O(V).

Esplora altri modi per misurare la complessità degli algoritmi nel tutorial Analyzing Complexity of Code through Python.

Applicazioni reali della Depth-First Search

La DFS è utile in molti campi, tra cui informatica, AI e sviluppo di videogiochi. Dai un’occhiata alla tabella qui sotto per alcune applicazioni comuni della DFS.

Depth-First Search vs altri algoritmi di ricerca

Confrontiamo la DFS con altri algoritmi noti come la breadth-first search, l’algoritmo di Dijkstra e A*.

Depth-first search versus breadth-first search

La breadth-first search (BFS) esplora un grafo livello per livello, visitando tutti i nodi alla profondità corrente prima di passare alla successiva. La BFS è particolarmente utile quando l’obiettivo è trovare il percorso più breve in un grafo non pesato. Tuttavia, la BFS può usare molta memoria, specialmente in grafi ampi, perché deve tenere traccia di tutti i nodi a ciascun livello. La BFS è un’ottima scelta per l’analisi delle reti sociali o per semplici problemi di instradamento.

La depth-first search, invece, è utile quando l’obiettivo è esplorare tutti i possibili percorsi o soluzioni, ad esempio nella risoluzione di puzzle o nel rilevamento di cicli in un grafo. A differenza della BFS, la DFS non garantisce il percorso più breve. Ma è più efficiente in termini di memoria, poiché tiene traccia solo del percorso corrente.

Puoi saperne di più sulla breadth-first search Breadth-First Search: A Beginner’s Guide with Python Examples.

DFS versus algoritmo di Dijkstra

L’algoritmo di Dijkstra è progettato per trovare il percorso più breve in grafi con archi pesati, dove ogni collegamento tra nodi ha un costo associato. Dijkstra esplora sempre per primo il percorso a costo minore, garantendo di trovare il percorso ottimale dal nodo iniziale a qualsiasi altro nodo. Tuttavia, può essere più lento della DFS in alcune esplorazioni semplici di grafi. Dijkstra è perfetto per compiti in cui i pesi degli archi contano, come le reti stradali o problemi di instradamento più complessi.

La depth-first search non tiene conto dei pesi degli archi, quindi non garantisce il percorso ottimale. Tuttavia, è più veloce di Dijkstra in grafi non pesati o quando i pesi degli archi sono irrilevanti.

Puoi saperne di più sull’algoritmo di Dijkstra in Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial.

DFS versus A*

A* (pronunciato “A-star”) è un algoritmo che migliora Dijkstra incorporando una euristica per guidare la ricerca. Questo lo rende più veloce ed efficiente in molti casi. A* bilancia tra l’esplorazione dei percorsi a costo minore (come Dijkstra) e l’avanzamento diretto verso l’obiettivo, usando una euristica come la distanza in linea d’aria. Questo rende A* molto efficiente per compiti come la navigazione GPS o il pathfinding nei videogiochi.

La depth-first search non usa alcuna euristica, il che significa che le manca la “direzione” che A* utilizza per raggiungere l’obiettivo in modo efficiente. La DFS è più adatta a problemi che richiedono una ricerca approfondita dell’intero grafo o albero decisionale, mentre A* è migliore quando serve trovare in modo efficiente il percorso più breve con l’aiuto di una euristica.

Errori comuni e come evitarli

Usando la depth-first search possono emergere diversi problemi comuni, soprattutto con grafi grandi.

Non tracciare i nodi visitati

Un problema si presenta quando ci si dimentica di tracciare quali nodi sono già stati visitati. Questo può portare a loop infiniti, specialmente nei grafi che contengono cicli. Quando la DFS rivisita nodi senza controllare se sono già stati esplorati, può rimanere bloccata in un loop infinito. Per evitarlo, assicurati di mantenere un elenco dei nodi visitati. Prima di visitare un nuovo nodo, controlla se è già nel set dei visitati. Se lo è, puoi tranquillamente saltarlo ed evitare di rimanere intrappolato.

Stack overflow nella DFS ricorsiva

In Python, la profondità di ricorsione è limitata a circa 1.000 livelli per impostazione predefinita, il che significa che chiamate ricorsive molto annidate in grafi grandi possono causare un RecursionError. Per prevenirlo, possiamo usare un’implementazione iterativa della DFS per grafi grandi. Gestendo lo stack come una lista, evitiamo i limiti della ricorsione e possiamo gestire in sicurezza grafi molto più grandi.

Scambiare una soluzione per il percorso più breve

È anche importante ricordare che la DFS non garantisce il percorso più breve tra due nodi. Poiché la DFS segue in profondità un percorso prima di tornare indietro per esplorarne altri, può trovare una soluzione, ma potrebbe non essere la più diretta.

Conclusione

La depth-first search è un potente algoritmo per esplorare e attraversare grafi e alberi. Grazie alla capacità di addentrarsi nei percorsi ed esplorare tutte le possibilità, è adatta a una varietà di problemi come la risoluzione di labirinti, la risoluzione di puzzle e l’esplorazione di alberi decisionali.

Se ti interessano gli algoritmi di ricerca, dai un’occhiata agli altri miei articoli della serie: Binary Search in Python: A Complete Guide for Efficient Searching e Breadth-First Search: A Beginner’s Guide with Python Examples. Potrebbero interessarti anche AVL Tree: Complete Guide With Python Implementation e Introduction to Network Analysis in Python.