Grafo: BFS e DFS
Grafo: BFS e DFS è un esperimento interattivo di Strutture dati, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
La ricerca in ampiezza (BFS) prende i nodi da una coda: visita prima tutti i vicini del nodo di partenza, poi i loro vicini, livello per livello, e così trova il cammino più breve in numero di archi. La ricerca in profondità (DFS) prende i nodi da una pila e va il più lontano possibile prima di tornare indietro. Entrambe visitano ogni nodo e arco una volta: O(V + E). BFS serve ai navigatori e agli «amici degli amici», DFS risolve labirinti e trova cicli.
Prova questo: Procedi passo passo dal nodo 0 e confronta la coda con la pila. Poi cambia il nodo di partenza in 7: l’ordine di visita cambia del tutto.
Domande frequenti
Che cosa mostra l’esperimento «Grafo: BFS e DFS»?
La ricerca in ampiezza (BFS) prende i nodi da una coda: visita prima tutti i vicini del nodo di partenza, poi i loro vicini, livello per livello, e così trova il cammino più breve in numero di archi. La ricerca in profondità (DFS) prende i nodi da una pila e va il più lontano possibile prima di tornare indietro. Entrambe visitano ogni nodo e arco una volta: O(V + E). BFS serve ai navigatori e agli «amici degli amici», DFS risolve labirinti e trova cicli.
Come provo «Grafo: BFS e DFS»?
Procedi passo passo dal nodo 0 e confronta la coda con la pila. Poi cambia il nodo di partenza in 7: l’ordine di visita cambia del tutto.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.