Cos'è l'algoritmo BFS (Breadth-First Search)?
La ricerca breadth-first (BFS) è un algoritmo utilizzato per rappresentare graficamente i dati o per cercare strutture ad albero o di attraversamento. La forma completa di BFS è la ricerca Breadth-first.
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 fino a quando tutti i nodi del grafico non sono stati visitati e contrassegnati con successo.
In questo tutorial sull'algoritmo imparerai:
- Cos'è l'algoritmo BFS (Breadth-First Search)?
- Che cosa sono le traversate del grafico?
- L'architettura dell'algoritmo BFS
- Perché abbiamo bisogno dell'algoritmo BFS?
- Come funziona l'algoritmo BFS?
- Algoritmo BFS di esempio
- Regole dell'algoritmo BFS
- Applicazioni dell'algoritmo BFS
Che cosa sono le traversate del grafico?
L'attraversamento del grafo è una metodologia comunemente usata per localizzare la posizione del vertice nel grafo. È 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 ogni nodo in un grafico senza essere bloccato in un ciclo infinito.
L'architettura dell'algoritmo BFS
- Nei vari livelli dei dati, è possibile contrassegnare qualsiasi nodo come nodo iniziale o iniziale per iniziare l'attraversamento. Il BFS visiterà il nodo, lo contrassegnerà come visitato e lo posizionerà nella coda.
- Ora il BFS visiterà i nodi più vicini e non visitati e li contrassegnerà. Questi valori vengono aggiunti anche alla coda. La coda funziona sul modello FIFO.
- In modo simile, i rimanenti nodi 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?
Esistono numerosi motivi per utilizzare l'algoritmo BFS da utilizzare per la ricerca del set di dati. Alcuni degli aspetti più vitali 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 alto livello di accuratezza rispetto ad altri algoritmi.
- Le iterazioni BFS sono senza soluzione di continuità e non vi è alcuna possibilità che questo algoritmo venga coinvolto in un problema di loop 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 o dal nodo iniziale in un grafico e lo attraversa completamente. Una volta che ha attraversato con successo il nodo iniziale, viene visitato e contrassegnato il vertice successivo 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 nel grafo è 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 alla coda BFS
Passaggio 3)
Avvia la ricerca BFS e, al termine, contrassegna il vertice V come visitato.
Passaggio 4)
La coda BFS non è ancora vuota, quindi rimuovere il vertice V del grafico dalla coda.
Passaggio 5)
Recupera tutti i vertici rimanenti sul grafico adiacenti al vertice V
Passaggio 6)
Per ogni vertice adiacente diciamo V1, nel caso non sia ancora visitato aggiungi V1 alla coda BFS
Passaggio 7)
BFS visiterà V1 e lo contrassegnerà come visitato e lo eliminerà dalla coda.
Algoritmo BFS di esempio
Passo 1)
Hai un grafico di sette numeri che vanno da 0 a 6.
Passo 2)
0 o zero è stato contrassegnato come nodo radice.
Passaggio 3)
0 viene visitato, contrassegnato e inserito nella struttura dati della coda.
Passaggio 4)
I rimanenti 0 nodi adiacenti e non visitati vengono visitati, contrassegnati e inseriti nella coda.
Passaggio 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 struttura dati di coda (FIFO-First in First Out) viene utilizzata da BFS.
- Contrassegni qualsiasi nodo nel grafico come root e inizi ad attraversare i dati da esso.
- BFS attraversa tutti i nodi nel grafico e continua a rilasciarli come completato.
- BFS visita un nodo adiacente non visitato, 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 esegue l'iterazione fino a quando tutti i vertici nel grafico non vengono attraversati correttamente 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 un'implementazione di algoritmo BFS può essere molto efficace.
- Grafici non pesati: 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 individuare tutti i nodi più vicini o vicini in una rete peer to peer. Questo troverà i dati richiesti più velocemente.
- Web crawler: i motori di ricerca o i web crawler possono facilmente creare più livelli di indici utilizzando BFS. L'implementazione di BFS inizia dalla fonte, che è 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.
- Network Broadcasting: un pacchetto trasmesso è guidato dall'algoritmo BFS per trovare e raggiungere tutti i nodi per i quali ha l'indirizzo.
Sommario
- Un attraversamento del grafo è un processo unico che richiede all'algoritmo di visitare, controllare e / o aggiornare ogni singolo nodo non visitato in una struttura ad albero. L'algoritmo BFS funziona su un principio simile.
- L'algoritmo è utile per analizzare i nodi in un grafo 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 inseriti in una coda da BFS. Una coda funziona su una base first in first out. Quindi, l'elemento posizionato 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'alta precisione e all'implementazione robusta, BFS viene utilizzato in più soluzioni di vita reale come reti P2P, Web Crawler e Network Broadcasting.