Ricerca in profondità (DFS)
Esplora un grafo seguendo un percorso il più a fondo possibile, poi torna all'ultimo bivio. La pila sullo schermo è quel percorso.
- tempo O(V + E)
- spazio O(V)
- usa una pila
Cosa significano questi termini?
- Vertice: un punto del grafo, disegnato qui come un cerchio con una lettera.
- Arco: una linea che unisce due vertici. Qui si può percorrere in entrambi i sensi.
- Vicini: i vertici uniti a un vertice da un arco. Si esaminano in ordine alfabetico.
- Coda: il primo che entra è il primo che esce. La BFS prende sempre il vertice che aspetta da più tempo.
- Pila: l'ultimo che entra è il primo che esce. La DFS riparte sempre dal vertice raggiunto per ultimo.
- V ed E: il numero di vertici e di archi. O(V + E) vuol dire che ogni vertice e ogni arco vengono trattati un numero fisso di volte.
- sulla pila
- attuale
- finito
- arco dell'albero di ricerca
- arco saltato
Si parte da A. Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli il grafo con cicli. Ogni arco tratteggiato riporta a un vertice già sulla pila o già finito: quell'arco chiude un ciclo.
Come funziona
La DFS chiama sé stessa sul primo vicino non ancora visto, poi sul primo vicino nuovo di quel vertice, e così via. Quando un vertice non ha più vicini nuovi, la sua chiamata finisce e la DFS torna indietro di un passo per provare il vicino successivo. Le chiamate aperte formano una pila, che è sempre il percorso dalla partenza al vertice attuale. Il numero accanto a un vertice è l'ordine in cui è stato visitato.
Quando conviene usarlo
Usa la DFS per scoprire cosa si può raggiungere, per trovare cicli, per attraversare un labirinto o per mettere in ordine compiti che dipendono l'uno dall'altro. Non trova il percorso più breve.