Visitato
In pila
Archi esaminati

  • Attuale
  • In pila
  • Completato
  • Percorso
Un clic su un nodo imposta

Di più sulla visita in profondità

Visita in profondità (DFS)

La visita in profondità esplora un grafo come chi percorre un labirinto tenendo una mano sul muro: segue un percorso fin dove arriva, e torna indietro solo quando non c'è più niente di nuovo. Per farlo usa una pila. Fai clic su un nodo per partire da lì, scegli un arrivo se vuoi, e procedi passo dopo passo per vedere la pila crescere e calare, ogni nodo ricevere il suo numero di visita e gli archi che chiudono un ciclo. Premi Avvia per guardare la visita, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per cercare un percorso fino a lì. Il numero su ogni nodo è l'ordine in cui è stato visitato, e la riga sotto il grafo è la pila, dalla partenza fino al nodo in cima. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Fai clic su un nodo per farne la partenza. Per cercare un percorso, passa il clic su Arrivo e fai clic su un altro nodo.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della visita.
  3. Osserva la pila sotto il grafo e il numero di visita su ogni nodo. Nuovo grafo crea un altro grafo da provare.

Come funziona la visita in profondità

Metti il nodo di partenza nella pila. Poi ripeti: guarda il prossimo vicino del nodo in cima alla pila. Un vicino non ancora visto riceve il numero di visita successivo, ricorda il nodo da cui è stato raggiunto e va in cima alla pila, così la visita riparte da lì. Quando il nodo in cima non ha più vicini da esaminare, è completato ed esce dalla pila, e la visita torna al nodo sottostante. Quando la pila è vuota, ogni nodo raggiungibile è stato visitato.

Cosa ti dice la pila

Poiché la visita riparte sempre dal nodo più recente, la pila è sempre un percorso dalla partenza al nodo che si sta esaminando. Quando l'arrivo viene raggiunto, la pila è un percorso fino a lì, anche se di solito non il più breve: quello lo trova la visita in ampiezza. In un grafo non orientato, un arco verso un nodo ancora nella pila, diverso da quello da cui si è appena arrivati, chiude un ciclo. I nodi ricordati formano un albero, l'albero della visita in profondità, e l'ordine in cui i nodi vengono completati è la chiave dell'ordinamento topologico.

Domande frequenti

Che cos'è la visita in profondità?

Un modo di esplorare un grafo da un nodo di partenza seguendo un percorso il più a fondo possibile, e tornando indietro per provare un altro ramo solo quando non c'è più niente di nuovo. Usa una pila, o la ricorsione, per ricordare la strada del ritorno.

La visita in profondità trova il percorso più breve?

No. Trova un percorso fino all'arrivo, se esiste, ma può essere molto più lungo del necessario, perché la DFS si impegna nel primo ramo che prova. Usa la visita in ampiezza per avere il minor numero di archi, o l'algoritmo di Dijkstra quando gli archi hanno una lunghezza.

Qual è la differenza tra DFS e BFS?

La visita in profondità usa una pila e va a fondo lungo un percorso prima di tornare indietro. La visita in ampiezza usa una coda e si allarga in modo uniforme, anello dopo anello. Entrambe visitano ogni nodo raggiungibile in un tempo che cresce con il numero di nodi più quello di archi; la BFS trova i percorsi più brevi, mentre la DFS è la scelta naturale per cicli, labirinti e ordinamento topologico.

Come trova un ciclo la DFS?

In un grafo non orientato, se la visita incontra un arco verso un nodo ancora nella pila, e quel nodo non è quello da cui è appena arrivata, l'arco chiude un anello. Nell'app, la riga di stato lo segnala quando succede.

Il mio grafo viene inviato da qualche parte?

No. Il grafo viene creato e visitato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor