I denne artikel vil vi diskutere BFS-algoritmen i datastrukturen. Bredde-først-søgning er en grafgennemløbsalgoritme, der begynder at krydse grafen fra rodknuden og udforsker alle naboknuderne. Derefter vælger den den nærmeste knude og udforsker alle de uudforskede knudepunkter. Mens du bruger BFS til traversering, kan enhver knude i grafen betragtes som rodknuden.
Der er mange måder at krydse grafen på, men blandt dem er BFS den mest brugte tilgang. Det er en rekursiv algoritme til at søge i alle hjørnerne i et træ- eller grafdatastruktur. BFS inddeler hvert hjørne af grafen i to kategorier - besøgte og ikke-besøgte. Den vælger en enkelt node i en graf og besøger derefter alle noder, der støder op til den valgte node.
Anvendelser af BFS-algoritme
Anvendelserne af bredde-først-algoritme er givet som følger -
- BFS kan bruges til at finde de nærliggende steder fra en given kildeplacering.
- I et peer-to-peer-netværk kan BFS-algoritmen bruges som en gennemløbsmetode til at finde alle de tilstødende noder. De fleste torrent-klienter, såsom BitTorrent, uTorrent osv. anvender denne proces til at finde 'frø' og 'peers' i netværket.
- BFS kan bruges i webcrawlere til at oprette websideindekser. Det er en af de vigtigste algoritmer, der kan bruges til at indeksere websider. Den begynder at krydse fra kildesiden og følger de links, der er knyttet til siden. Her betragtes hver webside som en node i grafen.
- BFS bruges til at bestemme den korteste vej og mindste spændingstræ.
- BFS bruges også i Cheneys teknik til at kopiere affaldsindsamlingen.
- Den kan bruges i ford-Fulkerson-metoden til at beregne det maksimale flow i et flownetværk.
Algoritme
Trinene involveret i BFS-algoritmen til at udforske en graf er givet som følger -
Trin 1: SET STATUS = 1 (klar tilstand) for hver node i G
Trin 2: Sæt startknudepunktet A i kø og indstil dens STATUS = 2 (ventetilstand)
Trin 3: Gentag trin 4 og 5, indtil KØ er tom
Trin 4: Sæt en node N i kø. Bearbejd den og indstil dens STATUS = 3 (behandlet tilstand).
Trin 5: Sæt alle naboerne til N i kø, der er i klar tilstand (hvis STATUS = 1) og indstil
deres STATUS = 2
(ventetilstand)
[SLUKKE SLUT]
Trin 6: AFSLUT
Eksempel på BFS-algoritme
Lad os nu forstå, hvordan BFS-algoritmen fungerer ved at bruge et eksempel. I eksemplet nedenfor er der en rettet graf med 7 hjørner.
I ovenstående graf kan minimumsti 'P' findes ved at bruge BFS'en, der starter fra Node A og slutter ved Node E. Algoritmen bruger to køer, nemlig QUEUE1 og QUEUE2. QUEUE1 rummer alle de noder, der skal behandles, mens QUEUE2 rummer alle de noder, der behandles og slettes fra QUEUE1.
Lad os nu begynde at undersøge grafen fra Node A.
Trin 1 - Først skal du tilføje A til kø1 og NULL til kø2.
QUEUE1 = {A} QUEUE2 = {NULL} Trin 2 - Nu skal du slette node A fra kø1 og tilføje den til kø2. Indsæt alle naboer til node A i kø1.
QUEUE1 = {B, D} QUEUE2 = {A} Trin 3 - Nu skal du slette node B fra kø1 og tilføje den til kø2. Indsæt alle naboer til node B i kø1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Trin 4 - Nu skal du slette node D fra kø1 og tilføje den til kø2. Indsæt alle naboer til node D i kø1. Den eneste nabo til Node D er F, da den allerede er indsat, så den vil ikke blive indsat igen.
java virtuel maskine
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Trin 5 - Slet node C fra kø1 og tilføj den til kø2. Indsæt alle naboer til node C i kø1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Trin 5 - Slet node F fra kø1 og tilføj den til kø2. Indsæt alle naboer til node F i kø1. Da alle naboerne til node F allerede er til stede, indsætter vi dem ikke igen.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Trin 6 - Slet node E fra kø1. Da alle dens naboer allerede er tilføjet, så vi vil ikke indsætte dem igen. Nu er alle noderne besøgt, og målknuden E stødes på i kø2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} BFS-algoritmens kompleksitet
Tidskompleksiteten af BFS afhænger af den datastruktur, der bruges til at repræsentere grafen. Tidskompleksiteten af BFS-algoritmen er O(V+E) , da BFS-algoritmen i værste fald udforsker hver node og kant. I en graf er antallet af hjørner O(V), hvorimod antallet af kanter er O(E).
Rumkompleksiteten af BFS kan udtrykkes som O(V) , hvor V er antallet af hjørner.
Implementering af BFS algoritme
Lad os nu se implementeringen af BFS-algoritmen i java.
I denne kode bruger vi nabolisten til at repræsentere vores graf. Implementering af Breadth-First Search-algoritmen i Java gør det meget nemmere at håndtere tilgrænsende liste, da vi kun skal rejse gennem listen over noder knyttet til hver node, når noden er sat ud af køen fra køens hoved (eller start).
I dette eksempel er grafen, som vi bruger til at demonstrere koden, givet som følger -
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;>