BFS
BFS
Cos’è
La classica visita in ampiezza (o per livello).
- SI parte da un vertice
- Scopri i vicini
- Prosegui la visita nei vertici scoperti
GOES WIDE ⇒ VA A LIVELLI
Possibili utilizzi
Permette di trovare:
- se un path esiste tra due nodi
- cammini minimi
- componenti connesse
- alberi di visita
Concetti fondamentali
Utilizza una CODA → FIFO Funziona in O(|V| + |E|) e in spazio O(|V|)
Funzionamento
La logica è:
- aggiungo alla coda il nodo iniziale
- mentre la coda non è vuota, prendo il primo nodo dalla coda
- se l’array dei nodi visitati non contiene il nodo preso poco fa, allora lo aggiungiamo alla lista dei nodi visitati
- per ogni nodo collegato al nodo di prima, se il nodo collegato non è già nella vista dei visitati mettilo in coda ⇒ torna al punto 2
- alla fine, nell’array dei visitati, avrò la mia visita in ampiezza