BFS (breadth-first search) è un metodo di attraversamento di grafi, molto spesso utilizzato in algoritmi sia semplici che avanzati. La ricerca in ampiezza funziona scorrendo i singoli livelli del grafico, partendo dal nodo sorgente e allontanandosi gradualmente da esso. Questo è chiaramente mostrato nell'animazione.
Per scrivere un semplice BFS, devi essere in grado di lavorare con una coda, una struttura di dati che ti permetta di prendere dall'inizio e metterlo alla fine, e anche essere in grado di memorizzare un grafico nel modulo di una lista di adiacenze.
Descrizione formale dell'algoritmo
1) Posiziona nella coda inizialmente vuota il numero del vertice da cui inizia la ricerca.
2) Estrai il vertice U dall'inizio della coda e contrassegnalo come utilizzato in un array separato.
3) Alla fine della coda, aggiungiamo tutti i vertici che possiamo raggiungere utilizzando lo spigolo dal vertice U e che non sono ancora segnati.
4) Se la coda è vuota, tutti i nodi del grafo connesso sono stati scansionati, altrimenti torna al passaggio 2.
Difficoltà di lavoro
Poiché, nel caso peggiore, l'algoritmo visita tutti i nodi del grafo, quando si memorizza il grafo sotto forma di liste di adiacenza, la complessità temporale dell'algoritmo è O(|V| + |E|), dove V è l'insieme dei vertici del grafico, ed E è l'insieme degli spigoli. ;
In altre parole, l'algoritmo funziona nel caso peggiore per il numero di spigoli + il numero di vertici.