Il breadth-first search (o ricerca in ampiezza) è un algoritmo utilizzato nella teoria dei grafi, il quale permette di partire da un nodo X ed espandere la ricerca come un raggio. L'implementazione di codesto algoritmo è simile alla ricerca in profondità (o DFS) ma al contrario, viene utilizzata come struttura dati ausiliaria una coda e non una pila.
Non sono qui a spiegare cos'è un grafo o una coda, ma bensì solo l'algoritmo. Magari più avanti posterò una guida su cosa sono.
Implementazione
Partendo da una lista di adiacenza l'algoritmo spingerà in coda tutti i nodi correlati finché essa non resterà vuota e tutti i nodi saranno stati esaminati. È giusto sottolineare che, nodi non correlati, non saranno mai esaminati. Nel secondo grafo dell'immagine qui sotto, i nodi 4 e 5, non saranno mai esaminati.
Per vedere se un nodo è stato visitato o meno si possono usare due strade diverse:
La complessità di suddetto algoritmo è O(|V|+|E|) ove V è il numero dei vertici e E il numero degli archi.
Pseudo codice
l'algoritmo utilizza anche la distanza come informazione degli archi
Codifica
Un esempio di caricamento della lista potrebbe essere:
Un esempio di esecuzione del programma potrebbe essere questa:
L'esempio che abbiano eseguito è quello della gif postata sopra.
La compilazione del programma deve avvenire con il flag -std=c++11.
Se vi si vuole usare una versione precedente, bisogna modificare:
in:
La guida è finita, spero di esservi stato d'aiuto
Non sono qui a spiegare cos'è un grafo o una coda, ma bensì solo l'algoritmo. Magari più avanti posterò una guida su cosa sono.
Implementazione
Partendo da una lista di adiacenza l'algoritmo spingerà in coda tutti i nodi correlati finché essa non resterà vuota e tutti i nodi saranno stati esaminati. È giusto sottolineare che, nodi non correlati, non saranno mai esaminati. Nel secondo grafo dell'immagine qui sotto, i nodi 4 e 5, non saranno mai esaminati.
Per vedere se un nodo è stato visitato o meno si possono usare due strade diverse:
- array di valori booleani (true se è stato visitato in precedenza; false se ancora no);
- array di valori interi con tre stati: BIANCO => non visitato; GRIGIO => in visita; NERO => già visitato).
La complessità di suddetto algoritmo è O(|V|+|E|) ove V è il numero dei vertici e E il numero degli archi.
Pseudo codice
l'algoritmo utilizza anche la distanza come informazione degli archi
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Codifica
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Un esempio di caricamento della lista potrebbe essere:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Un esempio di esecuzione del programma potrebbe essere questa:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
La compilazione del programma deve avvenire con il flag -std=c++11.
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Se vi si vuole usare una versione precedente, bisogna modificare:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
La guida è finita, spero di esservi stato d'aiuto
Ultima modifica:
