Struttura dei dati - Larghezza del primo attraversamento
L'algoritmo Breadth First Search (BFS) attraversa un grafico con un movimento in senso orizzontale e utilizza una coda per ricordare di ottenere il vertice successivo per avviare una ricerca, quando si verifica un vicolo cieco in qualsiasi iterazione.
Come nell'esempio riportato sopra, l'algoritmo BFS passa da A a B a E a F prima poi a C e G infine a D. Impiega le seguenti regole.
Rule 1- Visita il vertice adiacente non visitato. Contrassegnalo come visitato. Mostralo. Inseriscilo in una coda.
Rule 2 - Se non viene trovato alcun vertice adiacente, rimuovere il primo vertice dalla coda.
Rule 3 - Ripeti la Regola 1 e la Regola 2 fino a quando la coda non è vuota.
| Passo | Traversal | Descrizione |
|---|---|---|
| 1 |  |
Inizializza la coda. |
| 2 |  |
Partiamo dalla visita S (nodo iniziale) e contrassegnarlo come visitato. |
| 3 |  |
Vediamo quindi un nodo adiacente non visitato da S. In questo esempio, abbiamo tre nodi ma scegliamo alfabeticamenteA, contrassegnalo come visitato e accodalo. |
| 4 |  |
Successivamente, il nodo adiacente non visitato da S è B. Lo contrassegniamo come visitato e lo accodiamo. |
| 5 |  |
Successivamente, il nodo adiacente non visitato da S è C. Lo contrassegniamo come visitato e lo accodiamo. |
| 6 |  |
Adesso, Sviene lasciato senza nodi adiacenti non visitati. Quindi, rimuoviamo la coda e troviamoA. |
| 7 |  |
A partire dal A noi abbiamo Dcome nodo adiacente non visitato. Lo contrassegniamo come visitato e lo accodiamo. |
In questa fase, non ci sono nodi non contrassegnati (non visitati). Ma come per l'algoritmo continuiamo a rimuovere l'accodamento per ottenere tutti i nodi non visitati. Quando la coda si svuota, il programma è finito.
L'implementazione di questo algoritmo nel linguaggio di programmazione C può essere vista qui .