Complessità temporale e spaziale

Complessità temporale:

• O(V + E)
  • Ogni vertice viene inserito e rimosso dalla coda una volta, e ogni arco viene esaminato un numero costante di volte.

Complessità spaziale:

• O(V + E)
  • La lista di adiacenza memorizza ogni arco, mentre la coda e l'array dei vertici visitati possono contenere fino a V vertici.

Riepilogo:

• BFS esplora per livelli usando una coda e visita i vertici più vicini prima di quelli più lontani.
• Quest'ordine per livelli lo rende l'algoritmo di riferimento per trovare i percorsi più brevi nei grafi non pesati.