Què és BFS?

Breadth-First Search (BFS) es basa en travessar nodes afegint els veïns de cada node a la cua de recorregut a partir del node arrel. El BFS d'un gràfic és similar al d'un arbre, amb l'excepció que els gràfics poden tenir cicles. A diferència de la cerca en profunditat, tots els nodes veïns a una profunditat determinada s'investiguen abans de passar al següent nivell.

Algoritme BFS

A continuació es mostren els passos que s'han de seguir per utilitzar la cerca de l'amplada primer per explorar un gràfic:

1. Preneu les dades de la matriu d'adjacència del gràfic o de la llista d'adjacència.
2. Creeu una cua i ompliu-la amb elements.
3. Activeu el node arrel (és a dir, obteniu el node arrel al principi de la cua).
4. Traieu la cua el capçal de la cua (o l'element inicial) i, a continuació, col·loqueu tots els nodes propers de la cua d'esquerra a dreta. Simplement retireu la cua del cap i reinicieu l'operació si un node no té cap node proper que s'hagi d'investigar. (Nota: si apareix un veí que s'ha investigat prèviament o està a la cua, no el poseu a la cua; en canvi, ometeu-lo).
5. Continueu d'aquesta manera fins que la cua estigui buida.

Aplicacions BFS

A causa de la flexibilitat de l'algoritme, Breadth-First Search és força útil al món real. Aquests són alguns d'ells:

1. En una xarxa peer-to-peer, es descobreixen nodes peer. La majoria de clients de torrent, com BitTorrent, uTorrent i qBittorent, utilitzen aquest procés per trobar 'llavors' i 'peers' a la xarxa.
2. L'índex es construeix mitjançant tècniques de recorregut de gràfics en el rastreig web. El procediment comença amb la pàgina d'origen com a node arrel i va cap a totes les pàgines secundàries que estan enllaçades a la pàgina d'origen (i aquest procés continua). A causa de la profunditat reduïda de l'arbre de recursivitat, Breadth-First Search té un avantatge inherent aquí.
3. L'ús de sistemes de navegació GPS que utilitzen el GPS, realitzen una cerca en amplitud per localitzar llocs propers.
4. La tècnica de Cheney, que utilitza el concepte de cerca en amplitud, s'utilitza per recollir les escombraries.

Exemple BFS Traversal

Per començar, mirem un exemple senzill. Començarem amb 0 com a node arrel i anirem cap avall pel gràfic.

Pas 1: Cua (0)

Cua

Pas 2: Treu la cua (0), la cua (1), la cua (3), la cua (4)

Cua

Pas 3: Treu la cua (1), posa en cua (2)

Cua

Pas 4: Treu la cua (3), Posa la cua (5). No tornarem a afegir 1 a la cua perquè ja s'ha explorat 0.

Cua

Pas 5: Treu la cua (4)

Cua

Pas 6: Treu la cua (2)

Cua

Pas 7: Treu la cua (5)

Cua

La cua està buida ara, així que aturarem el procés.

Programa Java de cerca Breadth-First

Hi ha diversos enfocaments per tractar el codi. Principalment parlarem dels passos implicats per implementar una primera cerca àmplia a Java. Es pot utilitzar una llista d'adjacència o una matriu d'adjacència per emmagatzemar gràfics; qualsevol mètode és acceptable. La llista d'adjacència s'utilitzarà per representar el nostre gràfic al nostre codi. Quan s'implementa l'algoritme de cerca Breadth-First a Java, és molt més fàcil tractar la llista d'adjacència, ja que només hem de viatjar per la llista de nodes connectats a cada node una vegada que el node s'ha retirat de la cua del capçal (o inici) del cua.

El gràfic utilitzat per demostrar el codi serà idèntic al que s'utilitza a l'exemple anterior.

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;>