I denne artikkelen vil vi diskutere BFS-algoritmen i datastrukturen. Bredde-først-søk er en grafoverløpsalgoritme som starter å krysse grafen fra rotnoden og utforsker alle nabonodene. Deretter velger den nærmeste node og utforsker alle de uutforskede nodene. Når du bruker BFS for traversering, kan enhver node i grafen betraktes som rotnoden.
Det er mange måter å krysse grafen på, men blant dem er BFS den mest brukte tilnærmingen. Det er en rekursiv algoritme for å søke i alle toppunktene i et tre- eller grafdatastruktur. BFS setter hvert toppunkt av grafen i to kategorier - besøkt og ikke-besøkt. Den velger en enkelt node i en graf og besøker deretter alle nodene ved siden av den valgte noden.
Anvendelser av BFS-algoritme
Anvendelsene av bredde-først-algoritme er gitt som følger -
- BFS kan brukes til å finne nærliggende steder fra en gitt kildeplassering.
- I et peer-to-peer-nettverk kan BFS-algoritmen brukes som en traverseringsmetode for å finne alle nabonodene. De fleste torrentklienter, som BitTorrent, uTorrent, etc. bruker denne prosessen for å finne 'frø' og 'peers' i nettverket.
- BFS kan brukes i webcrawlere for å lage nettsideindekser. Det er en av hovedalgoritmene som kan brukes til å indeksere nettsider. Den begynner å gå fra kildesiden og følger koblingene knyttet til siden. Her regnes hver nettside som en node i grafen.
- BFS brukes til å bestemme den korteste veien og minimumsspenningstreet.
- BFS brukes også i Cheneys teknikk for å duplisere søppelsamlingen.
- Den kan brukes i ford-Fulkerson-metoden for å beregne maksimal strømning i et strømningsnettverk.
Algoritme
Trinnene involvert i BFS-algoritmen for å utforske en graf er gitt som følger -
Trinn 1: SET STATUS = 1 (klar tilstand) for hver node i G
Steg 2: Sett startnoden A i kø og sett dens STATUS = 2 (ventetilstand)
Trinn 3: Gjenta trinn 4 og 5 til KØ er tom
Trinn 4: Sett en node N i kø. Behandle den og sett dens STATUS = 3 (behandlet tilstand).
Trinn 5: Sett i kø alle naboene til N som er i klar tilstand (hvis STATUS = 1) og sett
deres STATUS = 2
(ventetilstand)
[END OF LOOP]
Trinn 6: EXIT
Eksempel på BFS-algoritme
La oss nå forstå hvordan BFS-algoritmen fungerer ved å bruke et eksempel. I eksemplet nedenfor er det en rettet graf med 7 toppunkter.
I grafen ovenfor kan minimumsbane 'P' bli funnet ved å bruke BFS som starter fra Node A og slutter ved Node E. Algoritmen bruker to køer, nemlig QUEUE1 og QUEUE2. KØ1 inneholder alle nodene som skal behandles, mens KØ2 inneholder alle nodene som behandles og slettes fra KØ1.
La oss nå begynne å undersøke grafen fra node A.
Trinn 1 - Først legger du A til kø1 og NULL til kø2.
QUEUE1 = {A} QUEUE2 = {NULL} Steg 2 - Nå, slett node A fra kø1 og legg den til i kø2. Sett inn alle naboer til node A til kø1.
QUEUE1 = {B, D} QUEUE2 = {A} Trinn 3 - Nå, slett node B fra kø1 og legg den til i kø2. Sett inn alle naboer til node B i kø1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Trinn 4 - Nå, slett node D fra kø1 og legg den til i kø2. Sett inn alle naboer til node D i kø1. Den eneste naboen til Node D er F siden den allerede er satt inn, så den vil ikke bli satt inn igjen.
java virtuell maskin
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Trinn 5 - Slett node C fra kø1 og legg den til kø2. Sett inn alle naboer til node C til kø1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Trinn 5 - Slett node F fra kø1 og legg den til i kø2. Sett inn alle naboer til node F i kø1. Siden alle naboene til node F allerede er tilstede, vil vi ikke sette dem inn igjen.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Trinn 6 - Slett node E fra kø1. Siden alle naboene allerede er lagt til, så vi vil ikke sette dem inn igjen. Nå er alle nodene besøkt, og målnoden E blir møtt i kø2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Kompleksiteten til BFS-algoritmen
Tidskompleksiteten til BFS avhenger av datastrukturen som brukes til å representere grafen. Tidskompleksiteten til BFS-algoritmen er O(V+E) , siden i verste fall utforsker BFS-algoritmen hver node og kant. I en graf er antall toppunkter O(V), mens antall kanter er O(E).
Romkompleksiteten til BFS kan uttrykkes som O(V) , hvor V er antall toppunkter.
Implementering av BFS-algoritme
La oss nå se implementeringen av BFS-algoritmen i java.
I denne koden bruker vi tilgrensningslisten for å representere grafen vår. Implementering av Breadth-First Search-algoritmen i Java gjør det mye lettere å håndtere tilgrensningslisten siden vi bare trenger å reise gjennom listen over noder knyttet til hver node når noden er satt ut av køen fra toppen (eller starten) av køen.
I dette eksemplet er grafen som vi bruker for å demonstrere koden gitt 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;>