Visita in ampiezza (BFS)
Getta un sasso in uno stagno e le onde si allargano in anelli regolari. La visita in ampiezza esplora un grafo allo stesso modo: prima tutto ciò che dista un passo dalla partenza, poi tutto ciò che dista due passi, e così via. È proprio questo ordine semplice a farle trovare i percorsi più brevi.
L'idea
Un grafo è un insieme di nodi collegati da archi: luoghi e strade, persone e amicizie, caselle di un labirinto e i passaggi tra di esse. La visita in ampiezza risponde alla domanda: partendo da qui, cosa posso raggiungere, e in quanti passi al minimo? Tiene una coda dei nodi ancora da visitare. Prendere i nodi dalla testa e aggiungere quelli nuovi in fondo fa sì che i nodi siano trattati nell'ordine in cui sono stati scoperti.
Passo per passo
Metti la partenza in coda a distanza 0. Prendi il nodo in testa. Per ogni vicino non ancora visto, registra come distanza quella del nodo attuale più uno, ricorda il nodo attuale come quello da cui è stato raggiunto e aggiungilo in fondo alla coda. Salta i vicini già visti. Ripeti finché la coda è vuota o finché raggiungi l'arrivo.
Un esempio
Prendi un grafo con gli archi A–B, A–C, B–D, C–D, C–E e D–F, e parti da A. Togliendo A dalla coda si trovano B e C a distanza 1. Togliendo B si trova D a distanza 2. Togliendo C si vede che D era già stato visto, e si trova E a distanza 2. Togliendo D si trova F a distanza 3. E e F non portano nulla di nuovo, e la coda è vuota. Risalendo i nodi ricordati da F si ottiene F ← D ← B ← A, quindi un percorso più breve da A a F è A → B → D → F, lungo tre archi.
Perché le distanze sono giuste
Ogni nodo a distanza 1 entra in coda prima di qualsiasi nodo a distanza 2, ogni nodo a distanza 2 prima di qualsiasi nodo a distanza 3, e così via, perché i vicini di un nodo entrano in coda solo quando il nodo stesso ne esce. Quindi il primo percorso che raggiunge un nodo è uno con il minor numero di archi, e la BFS non deve mai correggere una distanza. Ogni nodo viene preso una volta e ogni arco esaminato da entrambe le estremità, quindi il lavoro cresce con il numero di nodi più il numero di archi.
Storia e usi
Konrad Zuse descrisse la visita in ampiezza nel 1945, in un lavoro sul suo linguaggio Plankalkül pubblicato solo nel 1972. Edward F. Moore la reinventò nel 1959 per trovare il percorso più breve per uscire da un labirinto, e C. Y. Lee la usò nel 1961 per tracciare le piste sui circuiti stampati. Oggi trova il minor numero di mosse nei rompicapi, i gradi di separazione nei social network, le pagine che un web crawler raggiunge per prime e la cella libera più vicina nei giochi. Quando gli archi hanno una lunghezza, l'algoritmo di Dijkstra la generalizza.
Esplorala
Apri l'app e premi Passo. Il nodo in visita è evidenziato, i nodi in attesa nella coda sono blu e i nodi visitati sono verdi, ciascuno con la sua distanza. La coda è mostrata sotto il grafo, con la testa per prima. Passa il clic su Arrivo e scegli un nodo per fermarti lì e vedere il percorso più breve, oppure crea un nuovo grafo con più nodi e archi.
Domande frequenti
Qual è la complessità temporale della BFS?
O(V + E) per V nodi (vertici) ed E archi: ogni nodo entra ed esce dalla coda una volta, e ogni arco viene esaminato da entrambe le estremità. Servono O(V) di memoria in più per la coda e le distanze.
Perché la BFS usa una coda?
Perché «il primo che entra è il primo che esce» tiene i nodi nell'ordine in cui sono stati scoperti, che è l'ordine della loro distanza. Con una pila, invece, la ricerca andrebbe prima in profondità: questa è la visita in profondità.
La BFS trova i percorsi più brevi nei grafi pesati?
Non in generale: conta gli archi, non la loro lunghezza. Per grafi pesati senza archi negativi, usa l'algoritmo di Dijkstra. Se ogni peso è 0 o 1, funziona una variante chiamata BFS 0-1.
Dove si usa la BFS?
Per risolvere rompicapi e labirinti con il minor numero di mosse, trovare gli amici degli amici nei social network, esplorare il web livello per livello, diffondere messaggi nelle reti e come base di altri algoritmi, ad esempio per trovare flussi massimi.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la visita in ampiezza