Chi esplora una grotta con un gomitolo di filo segue un metodo preciso: imbocca un cunicolo e va avanti finché può; quando trova un vicolo cieco torna indietro seguendo il filo fino all'ultimo bivio con una galleria non ancora esplorata, e riparte da lì. È esattamente la strategia della visita in profondità, o DFS (Depth-First Search).
Se la visita in ampiezza procede per anelli concentrici, la DFS va «a fondo» lungo un ramo prima di considerare le alternative. Non trova i cammini più corti, ma rivela la struttura del grafo: componenti, cicli, punti critici, ordini di dipendenza.
Ricorsione o pila
La forma più naturale della DFS è ricorsiva:
def dfs(adj, u, visitato):
visitato.add(u)
for v in adj[u]:
if v not in visitato:
dfs(adj, v, visitato)
La ricorsione usa implicitamente la pila delle chiamate: ogni chiamata in sospeso è un bivio a cui tornare. Su grafi grandi, però, la profondità della ricorsione può superare il limite del linguaggio (in Python il limite predefinito è di circa mille chiamate). In quei casi si usa una pila esplicita:
def dfs_iterativa(adj, s):
visitato = set()
pila = [s]
while pila:
u = pila.pop()
if u in visitato:
continue
visitato.add(u)
for v in adj[u]:
if v not in visitato:
pila.append(v)
return visitato
Notate la differenza con la BFS: basta sostituire la coda con una pila (l'ultimo che entra è il primo che esce) e l'esplorazione cambia completamente carattere. Qui il controllo avviene all'estrazione, perché un vertice può essere inserito più volte prima di essere visitato.
Il costo resta proporzionale a n + m con le liste di adiacenza.
Tempi di scoperta e di fine
Una DFS diventa davvero potente quando si annotano due istanti per ogni vertice: quando viene scoperto (si entra nella chiamata) e quando è finito (tutti i suoi vicini sono stati esplorati e si esce). Con un contatore globale si ottengono due numeri, d[u] e f[u].
Questi intervalli sono annidati come parentesi: per due vertici qualsiasi, o un intervallo contiene interamente l'altro (uno è discendente dell'altro nell'albero DFS), oppure i due intervalli sono disgiunti. Questa proprietà è alla base dell'ordinamento topologico e degli algoritmi per le componenti fortemente connesse.
Classificare gli archi
Durante la visita di un grafo orientato ogni arco (u, v) cade in una di quattro categorie:
- arco d'albero: v viene scoperto proprio attraverso questo arco;
- arco all'indietro: v è un antenato di u ancora in corso di visita;
- arco in avanti: v è un discendente di u già finito;
- arco trasversale: v è in un altro ramo, già finito.
La categoria che conta di più è la seconda: un grafo orientato contiene un ciclo se e solo se la DFS trova almeno un arco all'indietro.
Rilevare i cicli in pratica
Per un grafo orientato si usano tre colori: bianco (mai visto), grigio (in corso di visita, cioè sulla pila attuale), nero (finito). Se dalla visita di u si incontra un vicino grigio, si è trovato un ciclo.
È lo stesso controllo che fanno i sistemi di build o i gestori di pacchetti quando segnalano una «dipendenza circolare»: il pacchetto A richiede B, B richiede C, C richiede A. Ricostruendo la catena dei vertici grigi si può anche mostrare all'utente il ciclo esatto, che è molto più utile di un generico messaggio d'errore.
Nei grafi non orientati basta ricordare il vertice da cui si arriva: un vicino già visitato che non è il genitore indica un ciclo.
Componenti connesse
In un grafo non orientato, una DFS lanciata da un vertice visita esattamente la sua componente connessa. Per trovarle tutte si scorre l'elenco dei vertici e si avvia una nuova visita da ogni vertice non ancora raggiunto, assegnando un numero di componente diverso a ogni avvio.
Esempi concreti:
- in un'immagine binaria, le macchie di pixel adiacenti dello stesso colore sono componenti connesse (è il principio dello strumento «secchiello» nei programmi di grafica);
- in un insieme di account collegati da indirizzi email o dispositivi in comune, ogni componente raggruppa gli account che probabilmente appartengono alla stessa persona o organizzazione;
- in una rete elettrica o idrica, le componenti mostrano quali zone restano isolate dopo un guasto.
Ponti e punti di articolazione
Con i tempi di scoperta si calcola anche, per ogni vertice, il tempo più basso raggiungibile dal suo sottoalbero usando al massimo un arco all'indietro. Da questo valore si ricavano i ponti (archi la cui rimozione disconnette il grafo) e i punti di articolazione (vertici con la stessa proprietà). In una rete aziendale sono i collegamenti e i dispositivi che rappresentano un punto singolo di guasto: sapere dove sono è il primo passo per aggiungere ridondanza.
In sintesi
- La DFS esplora un ramo fino in fondo prima di tornare indietro, con ricorsione o pila esplicita.
- Il costo è proporzionale a n + m; sui grafi profondi conviene la versione iterativa.
- I tempi di scoperta e di fine formano intervalli annidati, base di molti altri algoritmi.
- Un arco all'indietro segnala un ciclo: è il controllo delle dipendenze circolari.
- Componenti connesse, ponti e punti di articolazione si trovano tutti con una DFS.
