BFS — Algoritmo di ricerca in ampiezza spiegato

La ricerca in ampiezza, o BFS, è un algoritmo per grafi che visita i nodi in ordine di distanza da un nodo iniziale. Controlla tutti i nodi che si trovano a un arco di distanza prima di passare a quelli che sono a due archi, poi a tre archi, e così via.

Questo ordine per livelli è l'idea chiave. Se il grafo è non pesato, oppure se ogni arco ha lo stesso costo, BFS fornisce anche la lunghezza del cammino minimo dal nodo iniziale a ogni nodo raggiungibile.

Cosa fa la Breadth-First Search

BFS usa una coda, cioè una struttura first-in, first-out. È la coda che mantiene l'ordine per livelli: i nodi scoperti prima vengono elaborati prima.

Lo schema tipico è:

• segnare il nodo iniziale come visitato
• inserirlo nella coda
• rimuovere il nodo in testa
• aggiungere ogni vicino non visitato in fondo alla coda
• ripetere finché la coda non è vuota

Se memorizzi anche il padre di ogni nodo, puoi ricostruire un cammino minimo al termine della ricerca.

Perché la coda crea i livelli

Supponi che il nodo $A$ sia quello iniziale. I suoi vicini diretti sono a distanza $1$ da $A$, quindi entrano per primi nella coda. Solo dopo che questi nodi sono stati elaborati entrano i loro vicini non visitati, il che significa che l'ondata successiva ha distanza $2$.

Per questo BFS raggruppa naturalmente i nodi in base alla distanza dal punto di partenza. Non sta stimando quale cammino sia breve. La coda obbliga la ricerca a completare tutti i cammini con meno archi prima di considerare quelli più lunghi.

Esempio di BFS: trovare il cammino minimo per numero di archi

Usa questo grafo:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Parti da $A$. La coda cambia così:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Ecco cosa significa:

Per prima cosa, elabora $A$, poi aggiungi $B$ e $C$. Successivamente, elabora $B$ e poi $C$, aggiungendo $D$ ed $E$. Dopo di che, elabora $D$ ed $E$, raggiungendo $F$.

Quindi l'ordine di visita di BFS è:

$$A,\ B,\ C,\ D,\ E,\ F$$

Le distanze da $A$ sono:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Questo mostra il vantaggio principale. BFS raggiunge $F$ a distanza $3$, quindi il cammino minimo da $A$ a $F$ usa $3$ archi. Un cammino minimo è $A \to B \to D \to F$. Un altro è $A \to C \to E \to F$.

Errori comuni con BFS

Pensare che BFS trovi sempre il cammino meno costoso

Questo è vero solo quando ogni arco ha lo stesso costo, oppure quando il grafo viene trattato come non pesato. Se gli archi hanno pesi diversi, BFS può trovare un cammino con meno archi ma con un costo totale più alto.

Segnare un nodo troppo tardi

Nella BFS standard, un nodo di solito viene segnato come visitato quando viene inserito in coda, non quando viene rimosso in seguito. Questo impedisce che lo stesso nodo venga aggiunto alla coda molte volte.

Confondere BFS e DFS

BFS esplora per livelli. La depth-first search, o DFS, continua a seguire un ramo prima di tornare indietro. Sono efficaci per rispondere bene a tipi di domande diversi.

Dimenticare che l'ordine può dipendere dall'ordine dei vicini

L'ordine esatto di visita all'interno dello stesso livello può cambiare a seconda di come sono elencati i vicini. Le garanzie sulle distanze restano valide, ma l'ordine di attraversamento può essere diverso.

Quando si usa la Breadth-First Search

BFS è utile quando ti interessa la raggiungibilità, l'attraversamento per livelli negli alberi o la lunghezza dei cammini minimi misurata come numero di archi.

Compare anche nei problemi di spazio degli stati in cui ogni mossa ha lo stesso costo. In questa condizione, BFS è spesso il modo più chiaro per trovare il numero minimo di mosse.

Un modo semplice per ricordare BFS

Pensa a BFS come a un'onda che si espande verso l'esterno a partire dal nodo iniziale. Ogni passo dell'onda aggiunge un arco in più di distanza.

Per provare una tua versione, disegna un piccolo grafo, scegli un nodo iniziale e scrivi la coda dopo ogni passaggio. Se vuoi fare un passo in più, risolvi un problema simile di attraversamento di grafi e verifica se l'affermazione sul cammino minimo resta valida quando il grafo è pesato.