Cos'è la ricerca in profondità (DFS)?

Question

Accepted Answer

**DFS** esplora un grafo andando il più possibile in profondità lungo ogni ramo prima di tornare indietro. Utilizza uno **stack** (spesso lo stack di chiamate via ricorsione) e visita un intero percorso prima di esplorare alternative.

## L'idea

Da un nodo, ricorri in un vicino non visitato e continua a scendere in profondità; quando rimani bloccato, torna indietro e prova un altro ramo.

## Esempio

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Struttura | queue | stack / ricorsione |
| Trova | percorso più breve (non pesato) | qualsiasi percorso |
| Memoria | O(V) frontier | O(profondità) |
| Utile per | percorsi più brevi, livelli | cicli, ordinamento topologico, componenti |

## Complessità

- **Tempo:** O(V + E). **Spazio:** O(V) (profondità ricorsione + visitati).

## Insidie

Grafi profondi possono causare overflow dello stack di ricorsione — usa uno stack esplicito. Traccia `visited` per gestire i cicli.

## Perché è importante

DFS è alla base della rilevazione di cicli, dell'ordinamento topologico, delle componenti connesse e della generazione di percorsi/labirinti.

La sua eleganza ricorsiva rende il codice su alberi e grafi conciso.

Sapere quando la ricerca in profondità batte quella in ampiezza è fondamentale per la fluidità negli algoritmi su grafi.

	BFS	DFS
Struttura	queue	stack / ricorsione
Trova	percorso più breve (non pesato)	qualsiasi percorso
Memoria	O(V) frontier	O(profondità)
Utile per	percorsi più brevi, livelli	cicli, ordinamento topologico, componenti