Introduzione all'algoritmo BFS
Per accedere e gestire i dati in modo efficiente, possono essere archiviati e organizzati in un formato speciale noto come struttura dei dati. Esistono molte strutture di dati come Stack, Array, Elenco collegato, Code, Alberi e Grafici ecc. In strutture di dati lineari, come Stack, Array, Elenco collegato e Coda, i dati sono organizzati in ordine lineare mentre, in non strutture di dati lineari come alberi e grafici, i dati sono organizzati gerarchicamente non in una sequenza. Il grafico è una struttura di dati non lineare che ha nodi e bordi. I nodi nel grafico possono anche essere definiti vertici di numero finito e i bordi sono le linee di collegamento tra due nodi qualsiasi.
Nel grafico sopra, i vertici possono essere rappresentati come V = (A, B, C, D, E) e i bordi possono essere definiti come
E = (AB, AC, CD, BE)
Cos'è l'algoritmo BFS?
Esistono generalmente due algoritmi utilizzati per l'attraversamento di un grafico. Sono algoritmi BFS (Breadth-First Search) e DFS (Depth First Search). Traversal of the Graph sta visitando esattamente una volta ogni vertice o nodo e bordo, in un ordine ben definito. Inoltre, è molto importante tenere traccia dei vertici che sono stati visitati in modo che lo stesso vertice non venga attraversato due volte. Nell'algoritmo Breath First Search, l'attraversamento inizia da un nodo o nodo di origine selezionato e l'attraversamento continua attraverso i nodi direttamente collegati al nodo di origine. In termini più semplici, nell'algoritmo BFS si dovrebbe prima spostare orizzontalmente e attraversare il livello corrente, dopo di che si dovrebbe passare al livello successivo.
Come funziona l'algoritmo BFS?
Facciamo l'esempio del grafico seguente.
Il compito importante a portata di mano è trovare il percorso più breve in un grafico mentre si attraversano i nodi. Quando attraversiamo un grafico, il vertice passa da uno stato non scoperto a uno stato scoperto e alla fine viene completamente scoperto. Va notato che è possibile rimanere bloccati ad un certo punto mentre si attraversa un grafico e un nodo può essere visitato due volte. Quindi possiamo usare un metodo per contrassegnare i nodi dopo che cambia lo stato di essere scoperto a completamente scoperto.
Possiamo vedere nell'immagine qui sotto che i nodi possono essere contrassegnati nei grafici man mano che vengono scoperti completamente contrassegnandoli con il nero. Possiamo iniziare dal nodo di origine e mentre la traversata avanza attraverso ciascun nodo, possono essere contrassegnati per essere identificati.
La traversata inizia da un vertice e poi viaggia verso i bordi in uscita. Quando un bordo raggiunge un vertice non scoperto, viene contrassegnato come scoperto. Ma quando un limite va a un vertice completamente scoperto o scoperto, viene ignorato.
Per un grafico diretto, ogni bordo viene visitato una volta e per il grafico non orientato, viene visitato due volte, ovvero una volta durante la visita di ciascun nodo. L'algoritmo da utilizzare viene deciso in base alla modalità di memorizzazione dei vertici rilevati. Nell'algoritmo BFS, la coda viene utilizzata dove viene scoperto per primo il vertice più vecchio, quindi si propaga attraverso i livelli dal vertice iniziale.
I passaggi vengono eseguiti per un algoritmo BFS
I passaggi seguenti vengono eseguiti per un algoritmo BFS.
- In un dato grafico, partiamo da un vertice, cioè nel diagramma sopra è il nodo 0. Il livello, in cui è presente questo vertice, può essere indicato come Livello 0.
- Il prossimo passo è trovare tutti gli altri vertici che sono adiacenti al vertice iniziale, ovvero il nodo 0 o immediatamente accessibili da esso. Quindi possiamo contrassegnare questi vertici adiacenti per essere presenti al Livello 1.
- È possibile raggiungere lo stesso vertice a causa di un loop nel grafico. Quindi, dovremmo viaggiare solo verso quei vertici che dovrebbero essere presenti nello stesso livello.
- Successivamente, viene contrassegnato il vertice principale dell'attuale vertice in cui ci troviamo. Lo stesso deve essere eseguito per tutti i vertici al Livello 1.
- Quindi il passo successivo è trovare tutti quei vertici che sono a un solo bordo di distanza da tutti i vertici che sono al Livello 1. Questi nuovi set di vertici saranno al Livello 2.
- Il processo sopra descritto viene ripetuto fino a quando tutti i nodi non vengono attraversati.
Esempio:
Prendiamo l'esempio del grafico seguente e comprendiamo come funziona l'algoritmo BFS. Generalmente, in un algoritmo BFS, viene utilizzata una coda per mettere in coda i nodi mentre si attraversano i nodi.
Nel grafico sopra, per prima cosa deve essere visitato il nodo 0 e questo nodo viene messo in coda nella coda seguente:
Dopo aver visitato il nodo 0, il nodo adiacente di 0, 1 e 2 viene messo in coda. La coda può essere rappresentata come di seguito: 
Quindi verrà visitato il primo nodo nella coda che è 2. Dopo aver visitato il nodo 2, la coda può essere rappresentata come di seguito:
Dopo aver visitato il nodo 2, 5 verrà messo in coda e poiché non vi sono nodi vicini non visitati per il nodo 5, anche se 5 viene messo in coda ma non verrà visitato due volte.
Successivamente, il primo nodo nella coda è 1 che verrà visitato. I nodi vicini 3 e 4 sono messi in coda. La coda è rappresentata come di seguito
Successivamente, il primo nodo nella coda è 5 e per questo nodo non ci sono più nodi vicini non visitati. Lo stesso vale per i nodi 3 e 4 per i quali non ci sono più nodi vicini non visitati.
Quindi tutti i nodi vengono attraversati e, infine, la coda diventa vuota.
Conclusione
L'algoritmo di ricerca dell'ampiezza presenta alcuni grandi vantaggi per consigliarlo. Una delle tante applicazioni dell'algoritmo BFS è calcolare il percorso più breve. Inoltre, viene utilizzato in rete per trovare nodi vicini e può essere trovato in siti di social network, trasmissione di rete e raccolta dei rifiuti. Gli utenti devono comprendere i requisiti e il modello di dati per utilizzarli per prestazioni migliori.
Articoli consigliati
Questa è stata una guida all'algoritmo BFS. Qui discutiamo il concetto, il funzionamento, i passaggi e l'esempio delle prestazioni in Algoritmo BFS. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -
- Che cos'è un avido algoritmo?
- Algoritmo di ray tracing
- Algoritmo di firma digitale
- Che cos'è l'ibernazione Java?
- Crittografia con firma digitale
- BFS VS DFS | Le 6 principali differenze con l'infografica