Visita in profondità (DFS)
Entra in un labirinto, vai avanti finché non trovi un vicolo cieco, poi torna all'ultimo bivio e prova la strada successiva. La visita in profondità esplora un grafo allo stesso modo. È uno degli algoritmi sui grafi più semplici, e la pila che tiene ti dice più di quanto potresti aspettarti.
L'idea
Un grafo è un insieme di nodi collegati da archi: stanze e porte, pagine web e link, attività e le attività da cui dipendono. La visita in profondità visita ogni nodo che può raggiungere da una partenza, ma in un ordine particolare: riparte sempre dal nodo raggiunto più di recente. Tiene una pila dei nodi in cui si trova. Un nodo nuovo va in cima, e un nodo esce solo quando tutto ciò che ha intorno è stato esplorato.
Passo dopo passo
Metti la partenza nella pila e dalle il numero di visita 1. Guarda il prossimo vicino del nodo in cima. Se non è ancora stato visto, dagli il numero di visita successivo, ricorda il nodo da cui è stato raggiunto e mettilo in cima alla pila. Se è già stato visto, saltalo. Quando il nodo in cima non ha più vicini da esaminare, è completato: toglilo e continua con il nodo sottostante. Fermati quando la pila è vuota o quando hai raggiunto l'arrivo.
Un esempio
Prendi un grafo con gli archi A–B, A–C, B–D, C–D, C–E e D–F, parti da A ed esamina i vicini in ordine alfabetico. Da A la visita va a B, da B a D, da D a C e da C a E, quindi la pila è A, B, D, C, E. Lungo il cammino, C vede A, che è ancora nella pila: l'arco C–A chiude il ciclo A, B, D, C. E non ha niente di nuovo, quindi è completato, poi C, e la visita torna a D, che ha ancora F. L'ordine di visita è A, B, D, C, E, F. Con E come arrivo, la DFS si ferma con il percorso A → B → D → C → E, quattro archi, anche se A → C → E ne richiede solo due.
A cosa serve
La pila è sempre un percorso dalla partenza al nodo attuale, e questo rende la DFS naturale per labirinti e rompicapi: è l'idea alla base del backtracking. In un grafo non orientato, un arco verso un nodo ancora nella pila chiude un ciclo. In un grafo orientato, elencare i nodi nell'ordine inverso a quello in cui vengono completati dà un ordine topologico, così ogni attività viene dopo quelle da cui dipende. La visita in profondità trova anche le componenti connesse, i ponti e i punti di articolazione, e la sua versione casuale è un modo classico per generare labirinti.
Storia
Nel XIX secolo il matematico francese Charles Pierre Trémaux descrisse un modo per uscire da qualsiasi labirinto segnando i passaggi: è una visita in profondità fatta con il gesso. Nel 1972 e nel 1973 Robert Tarjan e John Hopcroft mostrarono che la DFS risolve molti problemi sui grafi in tempo lineare, dalle componenti fortemente connesse alla verifica che un grafo si possa disegnare senza incroci. Ricevettero il Premio Turing 1986 anche per questo lavoro.
Provala
Apri l'app e premi Passo. Il nodo di cui si stanno esaminando i vicini è evidenziato, i nodi nella pila sono blu e quelli completati verdi, ognuno con il suo numero di visita. La pila è mostrata sotto il grafo, dalla partenza al nodo in cima. Osserva la riga di stato per vedere gli archi che chiudono un ciclo, e scegli un arrivo per vedere quanto può essere lungo il percorso trovato rispetto alla visita in ampiezza.
Domande frequenti
Qual è la complessità temporale della DFS?
O(V + E) per V nodi (vertici) ed E archi (edges, in inglese): ogni nodo entra ed esce dalla pila una volta, e ogni arco viene esaminato da entrambe le estremità. Servono O(V) di memoria in più per la pila e le marcature.
Perché la DFS usa una pila?
Perché con la regola l'ultimo che entra è il primo che esce la visita riparte dal nodo più recente e poi torna a quello precedente. La ricorsione fa lo stesso con la pila delle chiamate del programma. Con una coda, invece, la visita si allargherebbe anello dopo anello: questa è la visita in ampiezza.
La DFS ricorsiva è un problema per i grafi grandi?
Può esserlo: un percorso lungo significa una ricorsione profonda, e molti linguaggi limitano la profondità delle chiamate. Una versione iterativa con una pila esplicita evita quel limite e visita i nodi nello stesso ordine.
Dove si usa la DFS?
Per risolvere labirinti e rompicapi con il backtracking, trovare cicli, ordinare attività in base alle dipendenze (ordinamento topologico), trovare componenti connesse e fortemente connesse, generare labirinti, e nei compilatori e negli strumenti di build che percorrono grafi di dipendenze.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la visita in profondità