Immaginate di lanciare un sasso in uno stagno: le onde si allargano in cerchi concentrici, raggiungendo prima i punti vicini e poi quelli lontani. La visita in ampiezza, nota con la sigla inglese BFS (Breadth-First Search), esplora un grafo esattamente così. Parte da un vertice, visita tutti i suoi vicini, poi i vicini dei vicini, e così via, un «anello» alla volta.
È uno degli algoritmi più semplici sui grafi e, allo stesso tempo, uno dei più usati. Ha una proprietà preziosa: in un grafo senza pesi trova i cammini con il minor numero di archi.
L'idea: una coda
Il cuore della BFS è una coda (FIFO, il primo che entra è il primo che esce). Lo schema è questo:
- inserisci il vertice di partenza nella coda e segnalo come visitato;
- finché la coda non è vuota, estrai il primo vertice u;
- per ogni vicino v di u non ancora visitato, segnalo come visitato, ricorda che ci sei arrivato da u e inseriscilo in fondo alla coda.
Il fatto che la coda serva i vertici nell'ordine di arrivo garantisce che tutti i vertici a distanza 1 vengano estratti prima di quelli a distanza 2, che a loro volta precedono quelli a distanza 3.
from collections import deque
def bfs(adj, s):
dist = {s: 0}
padre = {s: None}
coda = deque([s])
while coda:
u = coda.popleft()
for v in adj[u]:
if v not in dist:
dist[v] = dist[u] + 1
padre[v] = u
coda.append(v)
return dist, padre
Un dettaglio che fa spesso la differenza: il vertice va marcato come visitato quando entra in coda, non quando esce. Altrimenti lo stesso vertice può essere inserito più volte, con spreco di tempo e memoria.
Ricostruire il cammino
Il dizionario padre memorizza, per ogni vertice raggiunto, da quale vertice ci si è arrivati. Per ricostruire il cammino più corto da s a un obiettivo t si parte da t e si risale di padre in padre fino a s, poi si inverte la sequenza. L'insieme degli archi (padre[v], v) forma un albero, detto albero BFS, che contiene un cammino minimo da s verso ogni vertice raggiungibile.
Quanto costa
Ogni vertice entra in coda al massimo una volta e, quando esce, si scorrono i suoi vicini. Con le liste di adiacenza il costo totale è proporzionale a n + m: lineare nella dimensione del grafo. Con una matrice di adiacenza diventa n², perché trovare i vicini richiede di scorrere un'intera riga.
La memoria aggiuntiva è dominata dalla coda e dai dizionari, quindi proporzionale a n. Su grafi molto «larghi», dove un livello contiene moltissimi vertici, la coda può diventare grande: è la principale controindicazione della BFS rispetto alla visita in profondità.
Perché trova i cammini più corti
Si può dimostrare per induzione sui livelli: quando un vertice v viene scoperto per la prima volta da u, dist[u] è già la distanza minima di u, e nessun vertice a distanza inferiore è rimasto da esplorare. Quindi dist[u] + 1 è la distanza minima di v.
Attenzione però: la garanzia vale solo se tutti gli archi «costano» uguale. Se gli archi hanno pesi diversi, il cammino con meno archi può essere più lungo in chilometri o in tempo. In quel caso serve l'algoritmo di Dijkstra, che si può vedere come una BFS in cui la coda semplice è sostituita da una coda di priorità.
Usi concreti
- Labirinti e griglie: ogni cella è un vertice e i vicini sono le celle adiacenti libere. La BFS trova il percorso con meno passi verso l'uscita.
- Gradi di separazione: in una rete sociale, la distanza BFS tra due persone è il numero minimo di intermediari.
- Raggiungibilità in rete: partendo da un host compromesso, una BFS sul grafo delle connessioni possibili mostra quali sistemi sono raggiungibili in uno, due o tre salti. Nell'analisi di un incidente è un modo ordinato per stabilire il perimetro.
- Web crawler: esplorare un sito livello per livello dalla home page permette di limitare la profondità e di dare priorità alle pagine più vicine.
- Grafi bipartiti: colorando alternativamente i livelli BFS con due colori, si scopre se il grafo è bipartito. Se un arco collega due vertici dello stesso colore, non lo è.
Varianti utili
BFS da più sorgenti
Si inseriscono in coda all'inizio più vertici di partenza, tutti con distanza 0. Il risultato è, per ogni vertice, la distanza dalla sorgente più vicina: per esempio la distanza di ogni casa dalla farmacia più vicina.
BFS 0-1
Se gli archi pesano solo 0 o 1, si usa una coda a doppia estremità: gli archi di peso 0 inseriscono in testa, quelli di peso 1 in fondo. Si ottengono i cammini minimi in tempo lineare, senza la coda di priorità di Dijkstra.
BFS bidirezionale
Si parte contemporaneamente dalla sorgente e dalla destinazione e ci si ferma quando le due esplorazioni si incontrano. In grafi con molti vicini per nodo riduce drasticamente i vertici visitati.
In sintesi
- La BFS esplora il grafo per livelli usando una coda FIFO.
- Nei grafi non pesati trova i cammini con il minor numero di archi.
- Il costo è proporzionale a n + m con le liste di adiacenza.
- Va marcato come visitato ogni vertice quando entra in coda, non quando esce.
- Varianti come BFS multisorgente, 0-1 e bidirezionale coprono molti casi pratici.
