In dit artikel bespreken we het BFS-algoritme in de datastructuur. Breadth-first search is een algoritme voor het doorlopen van grafieken dat de grafiek begint te doorkruisen vanaf het hoofdknooppunt en alle aangrenzende knooppunten verkent. Vervolgens selecteert het het dichtstbijzijnde knooppunt en onderzoekt het alle onontdekte knooppunten. Bij gebruik van BFS voor traversal kan elk knooppunt in de grafiek worden beschouwd als het hoofdknooppunt.
Er zijn veel manieren om de grafiek te doorlopen, maar onder deze is BFS de meest gebruikte benadering. Het is een recursief algoritme om alle hoekpunten van een boom- of grafiekdatastructuur te doorzoeken. BFS verdeelt elk hoekpunt van de grafiek in twee categorieën: bezocht en niet-bezocht. Het selecteert een enkel knooppunt in een grafiek en bezoekt daarna alle knooppunten die grenzen aan het geselecteerde knooppunt.
Toepassingen van het BFS-algoritme
De toepassingen van het breedte-eerst-algoritme worden als volgt gegeven:
- BFS kan worden gebruikt om de aangrenzende locaties vanaf een bepaalde bronlocatie te vinden.
- In een peer-to-peer-netwerk kan het BFS-algoritme worden gebruikt als een traversal-methode om alle aangrenzende knooppunten te vinden. De meeste torrent-clients, zoals BitTorrent, uTorrent, etc. gebruiken dit proces om 'seeds' en 'peers' in het netwerk te vinden.
- BFS kan in webcrawlers worden gebruikt om webpagina-indexen te maken. Het is een van de belangrijkste algoritmen die kunnen worden gebruikt om webpagina’s te indexeren. Het begint vanaf de bronpagina en volgt de links die aan de pagina zijn gekoppeld. Hier wordt elke webpagina beschouwd als een knooppunt in de grafiek.
- BFS wordt gebruikt om het kortste pad en de minimaal opspannende boom te bepalen.
- BFS wordt ook gebruikt in de techniek van Cheney om de afvalinzameling te dupliceren.
- Het kan worden gebruikt in de Ford-Fulkerson-methode om de maximale stroom in een stroomnetwerk te berekenen.
Algoritme
De stappen die betrokken zijn bij het BFS-algoritme om een grafiek te verkennen, worden als volgt gegeven:
Stap 1: SET STATUS = 1 (gereedstatus) voor elk knooppunt in G
Stap 2: Plaats het startknooppunt A in de wachtrij en stel de STATUS in op 2 (wachtstatus)
Stap 3: Herhaal stap 4 en 5 totdat WACHTRIJ leeg is
geen ingangssignaal
Stap 4: Haal een knooppunt N uit de wachtrij. Verwerk het en stel de STATUS in op 3 (verwerkte status).
Stap 5: Plaats alle buren van N die zich in de gereed-status bevinden (waarvan STATUS = 1) in de wachtrij en stel deze in
hun STATUS = 2
(wachtstaat)
[EINDE LUS]
Stap 6: UITGANG
Voorbeeld van BFS-algoritme
Laten we nu de werking van het BFS-algoritme begrijpen door een voorbeeld te gebruiken. In het onderstaande voorbeeld is er een gerichte graaf met 7 hoekpunten.
In de bovenstaande grafiek kan het minimumpad 'P' worden gevonden door de BFS te gebruiken die begint bij knooppunt A en eindigt bij knooppunt E. Het algoritme gebruikt twee wachtrijen, namelijk QUEUE1 en QUEUE2. QUEUE1 bevat alle knooppunten die moeten worden verwerkt, terwijl QUEUE2 alle knooppunten bevat die worden verwerkt en verwijderd uit QUEUE1.
Laten we nu beginnen met het onderzoeken van de grafiek, beginnend bij knooppunt A.
Stap 1 - Voeg eerst A toe aan wachtrij1 en NULL aan wachtrij2.
QUEUE1 = {A} QUEUE2 = {NULL} Stap 2 - Verwijder nu knooppunt A uit wachtrij1 en voeg het toe aan wachtrij2. Voeg alle buren van knooppunt A in wachtrij1 in.
JavaScript-operatoren
QUEUE1 = {B, D} QUEUE2 = {A} Stap 3 - Verwijder nu knooppunt B uit wachtrij1 en voeg het toe aan wachtrij2. Voeg alle buren van knooppunt B in wachtrij1 in.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Stap 4 - Verwijder nu knooppunt D uit wachtrij1 en voeg het toe aan wachtrij2. Voeg alle buren van knooppunt D in wachtrij1 in. De enige buur van Knooppunt D is F, aangezien deze al is ingevoegd en dus niet opnieuw zal worden ingevoegd.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Stap 5 - Verwijder knooppunt C uit wachtrij1 en voeg het toe aan wachtrij2. Voeg alle buren van knooppunt C in wachtrij1 in.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Stap 5 - Verwijder knooppunt F uit wachtrij1 en voeg het toe aan wachtrij2. Voeg alle buren van knooppunt F in wachtrij1 in. Omdat alle buren van knooppunt F al aanwezig zijn, zullen we ze niet opnieuw invoegen.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Stap 6 - Verwijder knooppunt E uit wachtrij1. Omdat alle buren al zijn toegevoegd, zullen we ze niet opnieuw invoegen. Nu worden alle knooppunten bezocht en wordt het doelknooppunt E aangetroffen in wachtrij2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Complexiteit van het BFS-algoritme
De tijdscomplexiteit van BFS hangt af van de datastructuur die wordt gebruikt om de grafiek weer te geven. De tijdscomplexiteit van het BFS-algoritme is O(V+E) , omdat in het ergste geval het BFS-algoritme elk knooppunt en elke rand onderzoekt. In een grafiek is het aantal hoekpunten O(V), terwijl het aantal randen O(E) is.
c programmareeksarray
De ruimtecomplexiteit van BFS kan worden uitgedrukt als O(V) , waarbij V het aantal hoekpunten is.
Implementatie van BFS-algoritme
Laten we nu eens kijken naar de implementatie van het BFS-algoritme in Java.
In deze code gebruiken we de aangrenzende lijst om onze grafiek weer te geven. Het implementeren van het Breadth-First Search-algoritme in Java maakt het veel gemakkelijker om met de aangrenzende lijst om te gaan, omdat we alleen door de lijst met knooppunten hoeven te reizen die aan elk knooppunt zijn gekoppeld zodra het knooppunt uit de wachtrij (of het begin) van de wachtrij is gehaald.
In dit voorbeeld wordt de grafiek die we gebruiken om de code te demonstreren als volgt weergegeven:
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;>