În acest articol, vom discuta despre algoritmul BFS în structura datelor. Căutarea pe lățime este un algoritm de traversare a graficului care începe să traverseze graficul de la nodul rădăcină și explorează toate nodurile învecinate. Apoi, selectează cel mai apropiat nod și explorează toate nodurile neexplorate. În timp ce utilizați BFS pentru traversare, orice nod din grafic poate fi considerat nod rădăcină.
Există multe modalități de a parcurge graficul, dar dintre acestea, BFS este abordarea cea mai frecvent utilizată. Este un algoritm recursiv pentru a căuta toate nodurile unei structuri de date arborescente sau grafice. BFS pune fiecare vârf al graficului în două categorii - vizitat și nevizitat. Selectează un singur nod într-un grafic și, după aceea, vizitează toate nodurile adiacente nodului selectat.
Aplicații ale algoritmului BFS
Aplicațiile algoritmului lățimea-întâi sunt date după cum urmează -
- BFS poate fi folosit pentru a găsi locațiile învecinate dintr-o locație sursă dată.
- Într-o rețea peer-to-peer, algoritmul BFS poate fi utilizat ca metodă de traversare pentru a găsi toate nodurile învecinate. Majoritatea clienților torrent, cum ar fi BitTorrent, uTorrent etc. folosesc acest proces pentru a găsi „seeds” și „peers” în rețea.
- BFS poate fi folosit în crawlerele web pentru a crea indecși de pagini web. Este unul dintre principalii algoritmi care pot fi folosiți pentru indexarea paginilor web. Începe să traverseze din pagina sursă și urmează link-urile asociate paginii. Aici, fiecare pagină web este considerată ca un nod în grafic.
- BFS este folosit pentru a determina calea cea mai scurtă și arborele de acoperire minim.
- BFS este, de asemenea, folosit în tehnica lui Cheney pentru a duplica colectarea gunoiului.
- Poate fi folosit în metoda Ford-Fulkerson pentru a calcula debitul maxim într-o rețea de curgere.
Algoritm
Pașii implicați în algoritmul BFS pentru a explora un grafic sunt dați după cum urmează -
Pasul 1: SET STATUS = 1 (stare gata) pentru fiecare nod din G
metoda java equals
Pasul 2: Puneți în coadă nodul de pornire A și setați-i STATUS = 2 (starea de așteptare)
Pasul 3: Repetați pașii 4 și 5 până când COADA este goală
Pasul 4: Scoateți în coadă un nod N. Procesați-l și setați-i STATUS = 3 (starea procesată).
Pasul 5: Puneți în coadă toți vecinii lui N care sunt în starea gata (a căror STATUS = 1) și setați
STAREA lor = 2
verilog întotdeauna
(starea de așteptare)
[Sfârșitul buclei]
Pasul 6: IEȘIRE
Exemplu de algoritm BFS
Acum, să înțelegem funcționarea algoritmului BFS folosind un exemplu. În exemplul de mai jos, există un grafic direcționat având 7 vârfuri.
svm
În graficul de mai sus, calea minimă „P” poate fi găsită utilizând BFS care va începe de la Nodul A și se va termina la Nodul E. Algoritmul folosește două cozi, și anume QUEUE1 și QUEUE2. QUEUE1 deține toate nodurile care urmează să fie procesate, în timp ce QUEUE2 deține toate nodurile care sunt procesate și șterse din QUEUE1.
Acum, să începem să examinăm graficul pornind de la Nodul A.
Pasul 1 - Mai întâi, adăugați A la coada1 și NULL la coada2.
QUEUE1 = {A} QUEUE2 = {NULL} Pasul 2 - Acum, ștergeți nodul A din coada1 și adăugați-l în coada2. Inserați toți vecinii nodului A în coada1.
QUEUE1 = {B, D} QUEUE2 = {A} Pasul 3 - Acum, ștergeți nodul B din coada1 și adăugați-l în coada2. Inserați toți vecinii nodului B în coada1.
dezarhivarea in linux
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Pasul 4 - Acum, ștergeți nodul D din coada1 și adăugați-l în coada2. Inserați toți vecinii nodului D în coada1. Singurul vecin al Nodului D este F, deoarece este deja inserat, deci nu va mai fi inserat.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Pasul 5 - Ștergeți nodul C din coada1 și adăugați-l în coada2. Inserați toți vecinii nodului C în coada1.
scanner java
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Pasul 5 - Ștergeți nodul F din coada1 și adăugați-l în coada2. Inserați toți vecinii nodului F în coada1. Deoarece toți vecinii nodului F sunt deja prezenți, nu le vom introduce din nou.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Pasul 6 - Ștergeți nodul E din coada1. Deoarece toți vecinii săi au fost deja adăugați, nu le vom introduce din nou. Acum, toate nodurile sunt vizitate, iar nodul țintă E este întâlnit în coada2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Complexitatea algoritmului BFS
Complexitatea temporală a BFS depinde de structura datelor utilizată pentru a reprezenta graficul. Complexitatea temporală a algoritmului BFS este O(V+E) , deoarece în cel mai rău caz, algoritmul BFS explorează fiecare nod și margine. Într-un grafic, numărul de vârfuri este O(V), în timp ce numărul de muchii este O(E).
Complexitatea spațială a BFS poate fi exprimată ca O(V) , unde V este numărul de vârfuri.
Implementarea algoritmului BFS
Acum, să vedem implementarea algoritmului BFS în java.
În acest cod, folosim lista de adiacență pentru a reprezenta graficul nostru. Implementarea algoritmului Breadth-First Search în Java face mult mai ușoară gestionarea listei de adiacență, deoarece trebuie să călătorim doar prin lista de noduri atașate fiecărui nod odată ce nodul este scos din coada de la începutul (sau începutul) cozii.
În acest exemplu, graficul pe care îl folosim pentru a demonstra codul este dat după cum urmează -
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's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>