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.
- tempo O(V + E)
- spazio O(V)
- usa una coda
Cosa significano questi termini?
- 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.
- Coda: il primo che entra è il primo che esce. La BFS prende sempre il vertice che aspetta da più tempo.
- Pila: l'ultimo che entra è il primo che esce. La DFS riparte sempre dal vertice raggiunto per ultimo.
- 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.
- in coda
- attuale
- finito
- arco dell'albero di ricerca
- arco saltato
Si parte da A. Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
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.