ALGORITMO BFS

In questo articolo discuteremo dell'algoritmo BFS nella struttura dei dati. La ricerca in ampiezza è un algoritmo di attraversamento del grafico che inizia ad attraversare il grafico dal nodo radice ed esplora tutti i nodi vicini. Quindi seleziona il nodo più vicino ed esplora tutti i nodi inesplorati. Durante l'utilizzo di BFS per l'attraversamento, qualsiasi nodo nel grafico può essere considerato come nodo radice.

Esistono molti modi per attraversare il grafico, ma tra questi BFS è l'approccio più comunemente utilizzato. È un algoritmo ricorsivo per cercare tutti i vertici di una struttura dati ad albero o grafico. BFS inserisce ogni vertice del grafico in due categorie: visitato e non visitato. Seleziona un singolo nodo in un grafico e, successivamente, visita tutti i nodi adiacenti al nodo selezionato.

Applicazioni dell'algoritmo BFS

Le applicazioni dell'algoritmo di ampiezza sono date come segue:

BFS può essere utilizzato per trovare le posizioni vicine da una determinata posizione di origine.
In una rete peer-to-peer, l'algoritmo BFS può essere utilizzato come metodo trasversale per trovare tutti i nodi vicini. La maggior parte dei client torrent, come BitTorrent, uTorrent, ecc., utilizzano questo processo per trovare 'seed' e 'peer' nella rete.
BFS può essere utilizzato nei web crawler per creare indici di pagine web. È uno dei principali algoritmi che possono essere utilizzati per indicizzare le pagine web. Inizia a spostarsi dalla pagina di origine e segue i collegamenti associati alla pagina. Qui, ogni pagina web è considerata come un nodo nel grafico.
BFS viene utilizzato per determinare il percorso più breve e lo spanning tree minimo.
BFS viene utilizzato anche nella tecnica di Cheney per duplicare la garbage collection.
Può essere utilizzato nel metodo Ford-Fulkerson per calcolare il flusso massimo in una rete di flusso.

Algoritmo

I passaggi coinvolti nell'algoritmo BFS per esplorare un grafico sono i seguenti:

Passo 1: SET STATUS = 1 (stato pronto) per ciascun nodo in G

Passo 2: Accodare il nodo iniziale A e impostarne lo STATUS = 2 (stato di attesa)

Passaggio 3: Ripetere i passaggi 4 e 5 finché la CODA non sarà vuota

Passaggio 4: Rimuovi dalla coda un nodo N. Elaboralo e imposta il suo STATUS = 3 (stato elaborato).

Passaggio 5: Accoda tutti i vicini di N che sono nello stato pronto (il cui STATUS = 1) e imposta

il loro STATO = 2

(stato di attesa)

[FINE DEL CICLO]

Passaggio 6: USCITA

Esempio di algoritmo BFS

Ora comprendiamo il funzionamento dell'algoritmo BFS utilizzando un esempio. Nell'esempio riportato di seguito, esiste un grafico diretto con 7 vertici.

metodo Java uguale

Nel grafico sopra, il percorso minimo 'P' può essere trovato utilizzando il BFS che inizierà dal Nodo A e terminerà al Nodo E. L'algoritmo utilizza due code, vale a dire QUEUE1 e QUEUE2. LA CODA1 contiene tutti i nodi che devono essere elaborati, mentre la CODA2 contiene tutti i nodi che vengono elaborati ed eliminati dalla CODA1.

Iniziamo ora ad esaminare il grafico partendo dal Nodo A.

Passo 1 - Innanzitutto, aggiungi A alla coda1 e NULL alla coda2.

 QUEUE1 = {A} QUEUE2 = {NULL}

Passo 2 - Ora elimina il nodo A dalla coda1 e aggiungilo alla coda2. Inserisci tutti i vicini del nodo A nella coda1.

 QUEUE1 = {B, D} QUEUE2 = {A}

Passaggio 3 - Ora elimina il nodo B dalla coda1 e aggiungilo alla coda2. Inserisci tutti i vicini del nodo B nella coda1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B}

Passaggio 4 - Ora elimina il nodo D dalla coda1 e aggiungilo alla coda2. Inserisci tutti i vicini del nodo D nella coda1. L'unico vicino del Nodo D è F poiché è già inserito, quindi non verrà inserito nuovamente.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D}

Passaggio 5 - Elimina il nodo C dalla coda1 e aggiungilo alla coda2. Inserisci tutti i vicini del nodo C nella coda1.

 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C}

Passaggio 5 - Elimina il nodo F dalla coda1 e aggiungilo alla coda2. Inserisci tutti i vicini del nodo F nella coda1. Poiché tutti i vicini del nodo F sono già presenti, non li inseriremo nuovamente.

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F}

Passaggio 6 - Elimina il nodo E dalla coda1. Poiché tutti i suoi vicini sono già stati aggiunti, non li inseriremo nuovamente. Ora tutti i nodi vengono visitati e il nodo di destinazione E viene incontrato nella coda2.

 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E}

Complessità dell'algoritmo BFS

La complessità temporale di BFS dipende dalla struttura dei dati utilizzata per rappresentare il grafico. La complessità temporale dell'algoritmo BFS è O(V+E) , poiché nel peggiore dei casi, l'algoritmo BFS esplora ogni nodo e bordo. In un grafico, il numero di vertici è O(V), mentre il numero di archi è O(E).

La complessità spaziale di BFS può essere espressa come O(V) , dove V è il numero di vertici.

Implementazione dell'algoritmo BFS

Ora vediamo l'implementazione dell'algoritmo BFS in Java.

In questo codice, utilizziamo la lista di adiacenza per rappresentare il nostro grafico. L'implementazione dell'algoritmo Breadth-First Search in Java rende molto più semplice gestire l'elenco di adiacenze poiché dobbiamo solo viaggiare attraverso l'elenco dei nodi collegati a ciascun nodo una volta che il nodo viene rimosso dalla testa (o dall'inizio) della coda.

In questo esempio, il grafico che stiamo utilizzando per dimostrare il codice è dato come segue:

 import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[vertex]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>

TechCodeview