Depth-First Search (DFS)

Il Depth-First Search è un algoritmo di esplorazione che si applica sia agli alberi sia ai grafi. L'idea è quella di partire da un nodo e visitare i figli il più profondamente possibile, tornando indietro solo quando non ci sono più nodi da esplorare lungo il percorso corrente.

🚀 Quando usarlo

Utilizza DFS quando:

• Devi attraversare o cercare dati all'interno di un grafo o un albero
• Vuoi verificare la presenza di cicli o componenti connesse
• Stai esplorando tutte le combinazioni possibili tramite backtracking
• Ti serve generare un ordine di visita (preorder, inorder, postorder)

🧰 Tipi principali di DFS

Tipo	Descrizione
Ricorsiva	Utilizza lo stack chiamate della funzione per tenere traccia dei nodi
Iterativa	Usa uno stack esplicito per simulare la ricorsione

✏️ Esempio classico: Visita preorder di un albero binario

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def dfs(node):
    if not node:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

✅ Complessità:

• Tempo: O(n) dove n è il numero di nodi
• Spazio: O(h) con h altezza dell'albero o dimensione massima dello stack

🧩 Problemi comuni

Nome	Difficoltà	Pattern	Link
Binary Tree Preorder Traversal	Easy	Ricorsiva	Leetcode #144
Number of Islands	Medium	Ricorsiva	Leetcode #200
Clone Graph	Medium	Iterativa	Leetcode #133

💡 Consigli utili

• Occhio alla gestione dello stack: nei grafi è fondamentale marcare i nodi già visitati
• Valuta sempre se la versione iterativa possa evitare problemi di stack overflow
• In presenza di alberi particolarmente sbilanciati, considera altre strategie o il passaggio ad una struttura bilanciata

📚 Continua con

👉 Breadth-First Search →