Cos'è il BFS?

La ricerca Breadth-First (BFS) si basa sull'attraversamento dei nodi aggiungendo i vicini di ciascun nodo alla coda di attraversamento a partire dal nodo radice. Il BFS di un grafico è simile a quello di un albero, con l'eccezione che i grafici possono avere cicli. A differenza della ricerca in profondità, tutti i nodi vicini ad una determinata profondità vengono esaminati prima di procedere al livello successivo.

Algoritmo BFS

Di seguito sono riportati i passaggi necessari per utilizzare la ricerca in ampiezza per esplorare un grafico:

1. Prendi i dati per la matrice di adiacenza del grafico o la lista di adiacenza.
2. Crea una coda e riempila con gli elementi.
3. Attiva il nodo radice (il che significa che ottieni il nodo radice all'inizio della coda).
4. Rimuovi dalla coda la testa della coda (o l'elemento iniziale), quindi accoda tutti i nodi vicini della coda da sinistra a destra. È sufficiente rimuovere dalla coda la testa e riprendere l'operazione se un nodo non ha nodi vicini che necessitano di essere esaminati. (Nota: se emerge un vicino che è stato precedentemente esaminato o che è in coda, non accodarlo; invece, saltalo.)
5. Procedi in questo modo finché la coda non sarà vuota.

Applicazioni BFS

A causa della flessibilità dell'algoritmo, la ricerca in ampiezza è molto utile nel mondo reale. Questi sono alcuni di loro:

1. In una rete peer-to-peer vengono scoperti i nodi peer. La maggior parte dei client torrent, come BitTorrent, uTorrent e qBittorent, utilizzano questo processo per trovare 'seed' e 'peer' nella rete.
2. L'indice è costruito utilizzando tecniche di attraversamento del grafico nel web crawling. La procedura inizia con la pagina di origine come nodo radice e prosegue fino a tutte le pagine secondarie collegate alla pagina di origine (e questo processo continua). A causa della profondità ridotta dell'albero di ricorsione, la ricerca in ampiezza presenta qui un vantaggio intrinseco.
3. L'uso di sistemi di navigazione GPS che utilizzano il GPS, effettua una ricerca in ampiezza per individuare i siti vicini.
4. La tecnica di Cheney, che utilizza il concetto di ricerca in ampiezza, viene utilizzata per raccogliere i rifiuti.

Esempio di attraversamento BFS

Per iniziare, diamo un'occhiata a un semplice esempio. Inizieremo con 0 come nodo radice e procederemo verso il basso nel grafico.

Passo 1: Accoda(0)

Coda

Passo 2: Rimuovi dalla coda(0), Accoda(1), Accoda(3), Accoda(4)

dialetto ibernato

Coda

Passaggio 3: Rimuovi dalla coda(1), Accoda(2)

Coda

Passaggio 4: Rimuovi dalla coda(3), Accoda(5). Non aggiungeremo nuovamente 1 alla coda perché 0 è già stato esplorato.

Coda

Passaggio 5: Elimina coda(4)

Coda

Passaggio 6: Elimina coda(2)

Coda

viste e tabelle

Passaggio 7: Elimina coda(5)

Coda

La coda ora è vuota, quindi interromperemo il processo.

Programma Java di ricerca in ampiezza

Esistono diversi approcci per gestire il codice. Discuteremo principalmente i passaggi necessari per implementare una ricerca in ampiezza in Java. Per memorizzare i grafici è possibile utilizzare una lista di adiacenza o una matrice di adiacenza; entrambi i metodi sono accettabili. L'elenco di adiacenza verrà utilizzato per rappresentare il nostro grafico nel nostro codice. Quando si implementa l'algoritmo Breadth-First Search in Java, è molto più semplice gestire l'elenco di adiacenza 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) del nodo. coda.

Il grafico utilizzato per dimostrare il codice sarà identico a quello utilizzato nell'esempio precedente.

BFSTraversal.java

 import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; 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[node]; 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(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>