Ricerca in ampiezza (BFS)
Esplora un grafo strato per strato. Una coda decide quale vertice viene dopo, quindi i vertici più vicini vengono sempre visitati per primi.
- O(V + E)
- spazio O(V)
- coda
V ed E: il numero di vertici e di archi. O(V + E) vuol dire che ogni vertice e ogni arco vengono trattati un numero fisso di volte.
Coda: il primo che entra è il primo che esce. La BFS prende sempre il vertice che aspetta da più tempo.
Altri termini in questa pagina
- Vertice: un punto del grafo, disegnato qui come un cerchio con una lettera.
- Arco: una linea che unisce due vertici. Qui si può percorrere in entrambi i sensi.
- Vicini: i vertici uniti a un vertice da un arco. Si esaminano in ordine alfabetico.
Prova così: Scegli il grafo in due parti. I vertici non collegati alla partenza non vengono mai raggiunti.
Come funziona
La BFS mette il vertice di partenza in una coda. Poi, ancora e ancora, prende il vertice in testa alla coda e aggiunge i suoi vicini nuovi in fondo. Una coda serve in ordine di arrivo, quindi ogni vertice a un arco di distanza è finito prima di qualsiasi vertice a due archi. Il numero accanto a un vertice è la sua distanza dalla partenza: il minor numero di archi per raggiungerlo.
Quando conviene usarlo
Usa la BFS quando ti serve il percorso più breve in passi: meno mosse in un rompicapo, meno salti in una rete, le persone a due contatti da te. Su un grafo grande la coda può allungarsi molto, perché contiene un intero strato alla volta.