Algoritmo BFS (Breadth First Search) con ESEMPIO

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

Breadth-first search (BFS) è un algoritmo utilizzato per rappresentare graficamente i dati o cercare alberi o attraversare strutture. La forma completa di BFS è Breadth-first search.

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 iniziale o nodo iniziale da cui iniziare l'attraversamento. Il BFS visiterà il nodo e lo contrassegnerà come visitato e lo inserirà in 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. In modo simile, i nodi rimanenti più vicini e non visitati sul grafico vengono analizzati, contrassegnati e aggiunti alla coda. Questi elementi vengono eliminati dalla coda come ricevuti e stampati come risultato.

Perché abbiamo bisogno dell'algoritmo BFS?

Ci sono numerose ragioni per utilizzare l'algoritmo BFS per la ricerca del tuo dataset. Alcuni degli aspetti più importanti che rendono questo algoritmo la tua prima scelta 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.

Quindi, puoi dire che tutti i nodi adiacenti al vertice corrente vengono visitati e attraversati nella prima iterazione. Una semplice metodologia di coda viene utilizzata per implementare il funzionamento di un algoritmo BFS, e 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 non si acceda al vertice V, aggiungere il vertice V nella 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 sul grafico che sono adiacenti al vertice V

Passo 6)

Per ogni vertice adiacente diciamo V1, nel caso in cui non sia ancora stato visitato aggiungi V1 alla coda BFS

Passo 7)

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

Esempio di algoritmo BFS

Passo 1)

Hai 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 restanti 0 nodi adiacenti e non 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 le regole importanti per l'utilizzo dell'algoritmo BFS:

• Una coda (FIFO-First in First Out) struttura dati è utilizzato da BFS.
• Contrassegni qualsiasi nodo nel grafico come radice e inizi ad attraversare i dati 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 non venga trovato alcun vertice adiacente.
• L'algoritmo BFS esegue l'iterazione finché tutti i vertici del grafico 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 uno spanning tree minimo per visitare tutti i vertici del grafico nel minor tempo possibile con elevata precisione.
• Reti P2P: BFS può essere implementato per localizzare tutti i nodi più vicini o adiacenti in una rete peer to peer. Ciò troverà i dati richiesti più velocemente.
• 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.

Sintesi

• Un attraversamento del grafico è un processo unico che richiede che l'algoritmo visiti, controlli e/o aggiorni ogni singolo nodo non visitato in una struttura ad albero. L'algoritmo BFS funziona secondo un principio simile.
• L'algoritmo è utile per analizzare i nodi in un grafico e costruire il percorso più breve per attraversarli.
• L'algoritmo attraversa il grafico nel minor numero di iterazioni e nel minor tempo possibile.
• BFS seleziona un singolo nodo (punto iniziale o sorgente) in un grafico e quindi visita tutti i nodi adiacenti al nodo selezionato. BFS accede a questi nodi uno per uno.
• I dati visitati e contrassegnati vengono messi in coda da BFS. Una coda funziona in base al principio "first in first out". Pertanto, l'elemento inserito per primo nel grafico viene eliminato per primo e stampato di conseguenza.
• L'algoritmo BFS non può mai rimanere intrappolato in un ciclo infinito.
• Grazie all'elevata precisione e alla solida implementazione, BFS viene utilizzato in molteplici soluzioni reali come reti P2P, web crawler e trasmissione di rete.