I den här artikeln kommer vi att diskutera BFS-algoritmen i datastrukturen. Bredd-först-sökning är en grafgenomgångsalgoritm som börjar korsa grafen från rotnoden och utforskar alla närliggande noder. Sedan väljer den närmaste nod och utforskar alla outforskade noder. När du använder BFS för traversering kan vilken nod som helst i grafen betraktas som rotnoden.
Det finns många sätt att gå igenom grafen, men bland dem är BFS den mest använda metoden. Det är en rekursiv algoritm för att söka i alla hörn i ett träd eller grafdatastruktur. BFS placerar varje hörn av grafen i två kategorier - besökta och icke-besökta. Den väljer en enda nod i en graf och besöker efter det alla noder intill den valda noden.
Tillämpningar av BFS-algoritm
Tillämpningarna av bredd-först-algoritm ges enligt följande -
- BFS kan användas för att hitta närliggande platser från en given källplats.
- I ett peer-to-peer-nätverk kan BFS-algoritmen användas som en genomgångsmetod för att hitta alla närliggande noder. De flesta torrentklienter, som BitTorrent, uTorrent, etc. använder denna process för att hitta 'frön' och 'peers' i nätverket.
- BFS kan användas i sökrobotar för att skapa webbsidesindex. Det är en av huvudalgoritmerna som kan användas för att indexera webbsidor. Den börjar gå från källsidan och följer länkarna som är kopplade till sidan. Här betraktas varje webbsida som en nod i grafen.
- BFS används för att bestämma den kortaste vägen och minsta spännträd.
- BFS används också i Cheneys teknik för att duplicera sophämtningen.
- Den kan användas i ford-Fulkerson-metoden för att beräkna det maximala flödet i ett flödesnätverk.
Algoritm
Stegen som ingår i BFS-algoritmen för att utforska en graf ges enligt följande -
Steg 1: SET STATUS = 1 (färdigt tillstånd) för varje nod i G
Steg 2: Ställ startnoden A i kö och ställ in dess STATUS = 2 (vänteläge)
Steg 3: Upprepa steg 4 och 5 tills KÖ är tom
Steg 4: Ta ur kö för en nod N. Bearbeta den och ställ in dess STATUS = 3 (bearbetat tillstånd).
Steg 5: Ställ i kö alla grannar till N som är i redoläge (vars STATUS = 1) och ställ in
sträng och delsträng
deras STATUS = 2
(vänteläge)
arraylängd java
[SLUT PÅ LOOP]
Steg 6: UTGÅNG
Exempel på BFS-algoritm
Låt oss nu förstå hur BFS-algoritmen fungerar genom att använda ett exempel. I exemplet nedan finns en riktad graf med 7 hörn.
I diagrammet ovan kan minsta sökväg 'P' hittas genom att använda BFS som börjar från Nod A och slutar vid Nod E. Algoritmen använder två köer, nämligen QUEUE1 och QUEUE2. QUEUE1 innehåller alla noder som ska bearbetas, medan QUEUE2 innehåller alla noder som bearbetas och tas bort från QUEUE1.
Låt oss nu börja undersöka grafen från Nod A.
Steg 1 - Lägg först till A till kö1 och NULL till kö2.
QUEUE1 = {A} QUEUE2 = {NULL} Steg 2 - Ta nu bort nod A från kö1 och lägg till den i kö2. Infoga alla grannar till nod A i kö1.
QUEUE1 = {B, D} QUEUE2 = {A} Steg 3 - Ta nu bort nod B från kö1 och lägg till den i kö2. Infoga alla grannar till nod B i kö1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Steg 4 - Ta nu bort nod D från kö1 och lägg till den i kö2. Infoga alla grannar till nod D i kö1. Den enda granne till Nod D är F eftersom den redan är insatt, så den kommer inte att infogas igen.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Steg 5 - Ta bort nod C från kö1 och lägg till den i kö2. Infoga alla grannar till nod C i kö1.
understryka med css
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Steg 5 - Ta bort nod F från kö1 och lägg till den i kö2. Infoga alla grannar till nod F i kö1. Eftersom alla grannar till nod F redan är närvarande, kommer vi inte att infoga dem igen.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Steg 6 - Ta bort nod E från kö1. Eftersom alla dess grannar redan har lagts till, så vi kommer inte att infoga dem igen. Nu besöks alla noder och målnoden E påträffas i kö2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} BFS-algoritmens komplexitet
Tidskomplexiteten för BFS beror på den datastruktur som används för att representera grafen. Tidskomplexiteten för BFS-algoritmen är O(V+E) , eftersom BFS-algoritmen i värsta fall utforskar varje nod och kant. I en graf är antalet hörn O(V), medan antalet kanter är O(E).
Rymdkomplexiteten hos BFS kan uttryckas som O(V) , där V är antalet hörn.
Implementering av BFS-algoritm
Låt oss nu se implementeringen av BFS-algoritmen i java.
I den här koden använder vi grannlistan för att representera vår graf. Implementering av Breadth-First Search-algoritmen i Java gör det mycket lättare att hantera närliggande lista eftersom vi bara behöver resa genom listan med noder som är kopplade till varje nod när noden har ställts ur kö från början (eller början) av kön.
I det här exemplet ges grafen som vi använder för att demonstrera koden enligt följande -
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;>