Come funziona?

BFS mantiene un indicatore visited per ogni vertice e una queue di vertici da elaborare.

Procedura passo passo:

1. Contrassegna il vertice iniziale come visitato e inseriscilo nella coda.
2. Estrai il vertice in testa alla coda e registralo nell’ordine di visita.
3. Per ogni vicino non visitato (in ordine crescente), contrassegnalo come visitato e inseriscilo nella coda. Contrassegnare un vertice al momento dell’inserimento nella coda impedisce che venga aggiunto due volte.
4. Ripeti finché la coda non è vuota.

Esempio con i vertici 0..3 e gli archi [0,1, 0,2, 1,3, 2,3], partendo da 0:

• Visita 0, inserisci 1 e 2 nella coda; visita 1, inserisci 3 nella coda; visita 2; visita 3.
• Ordine di visita: [0, 1, 2, 3] (confrontalo con DFS: [0, 1, 3, 2]).