Motivazione

BFS usa una coda (primo a entrare, primo a uscire) così che i vertici vengano elaborati esattamente nell'ordine in cui vengono scoperti, producendo un'esplorazione livello per livello.

Perché imparare BFS?

• Percorsi più brevi: in un grafo non pesato, BFS trova il percorso con il minor numero di archi dal punto di partenza a ogni altro vertice.
• Semplice e lineare: viene eseguito in O(V + E) con una coda e un contrassegno di visita.
• Ovunque: i percorsi più brevi nelle reti, le catene di parole, la risoluzione di labirinti e la visita degli alberi per livelli sono tutti esempi di BFS.

Come per DFS, accodiamo i vicini di un vertice in ordine crescente affinché i risultati siano prevedibili.