Ce este BFS?

Breadth-First Search (BFS) se bazează pe traversarea nodurilor prin adăugarea vecinilor fiecărui nod la coada de traversare pornind de la nodul rădăcină. BFS pentru un grafic este similar cu cel al unui arbore, cu excepția faptului că graficele pot avea cicluri. Spre deosebire de căutarea în adâncime, toate nodurile vecine la o anumită adâncime sunt investigate înainte de a trece la nivelul următor.

Algoritmul BFS

Următorii sunt pașii implicați în utilizarea căutării pe lățimea întâi pentru a explora un grafic:

1. Luați datele pentru matricea de adiacență a graficului sau pentru lista de adiacență.
2. Creați o coadă și umpleți-o cu articole.
3. Activați nodul rădăcină (adică obțineți nodul rădăcină la începutul cozii).
4. Scoateți în coadă capul cozii (sau elementul inițial), apoi puneți în coadă toate nodurile din apropiere ale cozii de la stânga la dreapta. Pur și simplu scoateți din coadă capul și reluați operațiunea dacă un nod nu are noduri în apropiere care să fie investigate. (Notă: dacă apare un vecin care a fost investigat anterior sau este în coadă, nu-l puneți în coadă; în schimb, omiteți-l.)
5. Continuați în acest mod până când coada este goală.

Aplicații BFS

Datorită flexibilității algoritmului, Breadth-First Search este destul de utilă în lumea reală. Acestea sunt câteva dintre ele:

1. Într-o rețea peer-to-peer, nodurile peer sunt descoperite. Majoritatea clienților torrent, cum ar fi BitTorrent, uTorrent și qBittorent, folosesc acest proces pentru a găsi „seeds” și „peers” în rețea.
2. Indexul este construit folosind tehnici de traversare a graficelor în crawling-ul web. Procedura începe cu pagina sursă ca nod rădăcină și continuă până la toate paginile secundare care sunt legate la pagina sursă (și acest proces continuă). Din cauza adâncimii reduse a arborelui recursiv, Breadth-First Search are un avantaj inerent aici.
3. Utilizarea sistemelor de navigație GPS care utilizează GPS-ul efectuează o căutare pe lățime pentru a localiza site-urile din apropiere.
4. Tehnica lui Cheney, care folosește conceptul de căutare pe lățime, este folosită pentru a colecta gunoiul.

Exemplu de traversare BFS

Pentru a începe, să ne uităm la un exemplu simplu. Vom începe cu 0 ca nod rădăcină și vom merge în jos pe grafic.

Pasul 1: coadă(0)

Coadă

Pasul 2: Scoateți la coadă(0), Puneți în coadă(1), Puneți în coadă(3), Puneți în coadă(4)

Coadă

Pasul 3: Scoateți la coadă (1), puneți în coadă (2)

Coadă

Pasul 4: Scoatere la coadă (3), Pune la coadă (5). Nu vom adăuga din nou 1 la coadă deoarece 0 a fost deja explorat.

Coadă

Pasul 5: Scoateți la coadă (4)

Coadă

Pasul 6: Scoateți la coadă (2)

Coadă

Pasul 7: Scoateți la coadă (5)

unde este introducerea tastei pe tastatura laptopului

Coadă

Coada este goală acum, așa că vom opri procesul.

Programul Java de căutare Breadth-First

Există mai multe abordări de a trata codul. Vom discuta mai ales despre pașii implicați în implementarea unei prime căutări ample în Java. O listă de adiacență sau o matrice de adiacență poate fi utilizată pentru a stoca grafice; oricare metodă este acceptabilă. Lista de adiacență va fi folosită pentru a reprezenta graficul nostru în codul nostru. Când implementăm algoritmul Breadth-First Search în Java, este mult mai ușor să ne ocupăm de lista de adiacență, deoarece trebuie să călătorim prin lista de noduri atașate fiecărui nod doar odată ce nodul este scos din coada de la începutul (sau începutul) coadă.

Graficul folosit pentru a demonstra codul va fi identic cu cel folosit în exemplul 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;>