Algoritmo BFS (Breadth First Search) con ESEMPIO

Che cos'è l'algoritmo BFS (ricerca in ampiezza)?

La ricerca in ampiezza (BFS, Breadth-first search) è un algoritmo utilizzato per rappresentare graficamente i dati, per esplorare alberi o per attraversare strutture. L'acronimo BFS sta per Breadth-first search (ricerca in ampiezza).

L'algoritmo visita e contrassegna in modo efficiente tutti i nodi chiave in un grafico in modo accurato in larghezza. Questo algoritmo seleziona un singolo nodo (punto iniziale o sorgente) in un grafico e quindi visita tutti i nodi adiacenti al nodo selezionato. Ricorda, BFS accede a questi nodi uno per uno.

Una volta che l'algoritmo visita e contrassegna il nodo di partenza, si sposta verso i nodi non visitati più vicini e li analizza. Una volta visitati, tutti i nodi vengono contrassegnati. Queste iterazioni continuano finché tutti i nodi del grafico non sono stati visitati e contrassegnati con successo.

Che cosa sono gli attraversamenti del grafico?

L'attraversamento del grafico è una metodologia comunemente utilizzata per individuare la posizione del vertice nel grafico. Si tratta di un algoritmo di ricerca avanzato in grado di analizzare il grafico con velocità e precisione oltre a segnare la sequenza dei vertici visitati. Questo processo ti consente di visitare rapidamente ciascun nodo in un grafico senza rimanere bloccato in un ciclo infinito.

L'architettura dell'algoritmo BFS

1. Nei vari livelli dei dati, è possibile contrassegnare qualsiasi nodo come nodo di partenza o iniziale per iniziare l'attraversamento. L'algoritmo BFS visiterà il nodo, lo contrassegnerà come visitato e lo inserirà nella coda.
2. Ora il BFS visiterà i nodi più vicini e non visitati e li contrassegnerà. Questi valori vengono anche aggiunti alla coda. La coda funziona su Modello FIFO.
3. Analogamente, i nodi rimanenti più vicini e non ancora visitati sul grafo vengono analizzati, contrassegnati e aggiunti alla coda. Questi elementi vengono eliminati dalla coda man mano che vengono ricevuti e stampati come risultato.

Perché abbiamo bisogno dell'algoritmo BFS?

Esistono numerose ragioni per utilizzare l'algoritmo BFS per la ricerca nel tuo dataset. Alcuni degli aspetti più importanti che rendono questo algoritmo la scelta ideale sono:

• BFS è utile per analizzare i nodi in un grafico e costruire il percorso più breve per attraversarli.
• BFS può attraversare un grafico nel minor numero di iterazioni.
• L'architettura dell'algoritmo BFS è semplice e robusta.
• Il risultato dell'algoritmo BFS mantiene un elevato livello di precisione rispetto ad altri algoritmi.
• Le iterazioni BFS sono continue e non vi è alcuna possibilità che questo algoritmo rimanga intrappolato in un problema di ciclo infinito.

Come funziona l'algoritmo BFS?

L'attraversamento del grafico richiede che l'algoritmo visiti, controlli e/o aggiorni ogni singolo nodo non visitato in una struttura ad albero. Gli attraversamenti del grafico sono classificati in base all'ordine in cui visitano i nodi sul grafico.

L'algoritmo BFS avvia l'operazione dal primo nodo o nodo iniziale in un grafico e lo attraversa completamente. Una volta attraversato con successo il nodo iniziale, viene visitato e contrassegnato il successivo vertice non attraversato nel grafico.

Pertanto, si può affermare che tutti i nodi adiacenti al vertice corrente vengono visitati e attraversati nella prima iterazione. Per implementare il funzionamento di un algoritmo BFS viene utilizzata una semplice metodologia a coda, che consiste nei seguenti passaggi:

Passo 1)

Ogni vertice o nodo del grafico è noto. Ad esempio, puoi contrassegnare il nodo come V.

Passo 2)

Nel caso in cui il vertice V non sia accessibile, aggiungerlo alla coda BFS.

Passo 3)

Avvia la ricerca BFS e, al termine, contrassegna il vertice V come visitato.

Passo 4)

La coda BFS non è ancora vuota, quindi rimuovi il vertice V del grafico dalla coda.

Passo 5)

Recupera tutti i vertici rimanenti del grafo adiacenti al vertice V.

Passo 6)

Per ogni vertice adiacente, diciamo V1, se non è ancora stato visitato, aggiungi V1 alla coda BFS.

Passo 7)

BFS visiterà V1, lo contrassegnerà come visitato e lo eliminerà dalla coda.

Esempio di algoritmo BFS

Passo 1)

Hai a disposizione un grafico di sette numeri che vanno da 0 a 6.

Passo 2)

0 o zero è stato contrassegnato come nodo radice.

Passo 3)

0 viene visitato, contrassegnato e inserito nella struttura dati della coda.

Passo 4)

I nodi rimanenti adiacenti a 0 e non ancora visitati vengono visitati, contrassegnati e inseriti nella coda.

Passo 5)

Le iterazioni di attraversamento vengono ripetute finché non vengono visitati tutti i nodi.

Regole dell'algoritmo BFS

Ecco alcune regole importanti per l'utilizzo dell'algoritmo BFS:

• Una coda (FIFO – First in First Out) struttura dati è utilizzato da BFS.
• Si contrassegna un nodo qualsiasi del grafico come radice e si inizia a percorrere i dati a partire da esso.
• BFS attraversa tutti i nodi nel grafo e continua a lasciare cadereping li consideravano completati.
• BFS visita un nodo non visitato adiacente, lo contrassegna come completato e lo inserisce in una coda.
• Rimuove il vertice precedente dalla coda nel caso in cui non venga trovato alcun vertice adiacente.
• L'algoritmo BFS itera fino a quando tutti i vertici del grafo non vengono attraversati con successo e contrassegnati come completati.
• Non ci sono loop causati da BFS durante l'attraversamento dei dati da qualsiasi nodo.

Applicazioni dell'algoritmo BFS

Diamo un'occhiata ad alcune delle applicazioni reali in cui l'implementazione di un algoritmo BFS può essere molto efficace.

• Grafici non ponderati: L'algoritmo BFS può facilmente creare il percorso più breve e un albero di copertura minimo per visitare tutti i vertici del grafo nel minor tempo possibile e con elevata precisione.
• Reti P2P: L'algoritmo BFS può essere implementato per individuare tutti i nodi più vicini o adiacenti in una rete peer-to-peer. Ciò consentirà di trovare i dati richiesti più rapidamente.
• Crawler web: I motori di ricerca o i web crawler possono facilmente creare più livelli di indici utilizzando BFS. L'implementazione di BFS inizia dalla fonte, ovvero la pagina Web, e quindi visita tutti i collegamenti da quella fonte.
• Sistemi di navigazione: BFS può aiutare a trovare tutte le posizioni vicine dalla posizione principale o di origine.
• Trasmissione in rete: Un pacchetto trasmesso è guidato dall'algoritmo BFS per trovare e raggiungere tutti i nodi di cui ha l'indirizzo.

DOMANDE FREQUENTI