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:
- Preneu les dades de la matriu d'adjacència del gràfic o de la llista d'adjacència.
- Creeu una cua i ompliu-la amb elements.
- Activeu el node arrel (és a dir, obteniu el node arrel al principi de la cua).
- 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).
- 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:
- 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.
- 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í.
- L'ús de sistemes de navegació GPS que utilitzen el GPS, realitzen una cerca en amplitud per localitzar llocs propers.
- 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
| 0 |
Pas 2: Treu la cua (0), la cua (1), la cua (3), la cua (4)
Cua
| 1 | 3 | 4 |
Pas 3: Treu la cua (1), posa en cua (2)
Cua
| 3 | 4 | 2 |
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
| 4 | 2 | 5 |
Pas 5: Treu la cua (4)
Cua
| 2 | 5 |
Pas 6: Treu la cua (2)
Cua
| 5 |
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;>