Introduzione

Bentornato nella serie sugli algoritmi sui grafi! Dopo la ricerca in profondità (DFS), passiamo alla ricerca in ampiezza (BFS), l’altro algoritmo fondamentale per l’attraversamento dei grafi.

Mentre la DFS si addentra in profondità, la BFS esplora a livelli: prima il vertice di partenza, poi tutti i suoi vicini, poi tutti i vertici a due passi di distanza e così via. È proprio quest’ordine livello per livello che permette alla BFS di trovare i percorsi più brevi nei grafi non pesati.

Come nel resto della serie, un grafo è rappresentato da n (il numero di vertici, da 0 a n - 1) e da edges, un array piatto di coppie non orientate [u0, v0, u1, v1, ...].

Cominciamo!