V tem članku bomo razpravljali o algoritmu BFS v strukturi podatkov. Iskanje v širino je algoritem za prečkanje grafa, ki začne prečkati graf od korenskega vozlišča in raziskuje vsa sosednja vozlišča. Nato izbere najbližje vozlišče in razišče vsa neraziskana vozlišča. Pri uporabi BFS za prečkanje se lahko vsako vozlišče v grafu obravnava kot korensko vozlišče.
Obstaja veliko načinov za prečkanje grafa, vendar je med njimi najpogosteje uporabljen pristop BFS. Je rekurziven algoritem za iskanje po vseh točkah podatkovne strukture drevesa ali grafa. BFS vsako vozlišče grafa uvrsti v dve kategoriji - obiskano in neobiskano. Izbere posamezno vozlišče v grafu in nato obišče vsa vozlišča, ki mejijo na izbrano vozlišče.
Uporaba algoritma BFS
Uporabe algoritma najprej v širino so podane na naslednji način -
- BFS se lahko uporablja za iskanje sosednjih lokacij iz dane izvorne lokacije.
- V omrežju enakovrednih se lahko algoritem BFS uporablja kot metoda prehoda za iskanje vseh sosednjih vozlišč. Večina torrent odjemalcev, kot so BitTorrent, uTorrent itd., uporablja ta postopek za iskanje 'seed' in 'peers' v omrežju.
- BFS se lahko uporablja v spletnih pajkih za ustvarjanje indeksov spletnih strani. Je eden glavnih algoritmov, ki se lahko uporabljajo za indeksiranje spletnih strani. Začne se premikati od izvorne strani in sledi povezavam, povezanim s stranjo. Tu se vsaka spletna stran obravnava kot vozlišče v grafu.
- BFS se uporablja za določitev najkrajše poti in najmanjšega vpetega drevesa.
- BFS se uporablja tudi v Cheneyjevi tehniki za podvajanje zbiranja smeti.
- Uporablja se lahko v ford-Fulkersonovi metodi za izračun največjega pretoka v pretočni mreži.
Algoritem
Koraki, vključeni v algoritem BFS za raziskovanje grafa, so podani na naslednji način -
10 od 60
Korak 1: SET STATUS = 1 (stanje pripravljenosti) za vsako vozlišče v G
2. korak: Postavite začetno vozlišče A v čakalno vrsto in mu nastavite STATUS = 2 (čakalno stanje)
3. korak: Ponavljajte koraka 4 in 5, dokler QUEUE ni prazna
4. korak: Iz čakalne vrste odstranite vozlišče N. Obdelajte ga in mu nastavite STATUS = 3 (obdelano stanje).
ukaz autocad stretch
5. korak: Postavite v čakalno vrsto vse sosede N, ki so v stanju pripravljenosti (katerih STATUS = 1) in nastavite
njihov STATUS = 2
(čakalno stanje)
[KONEC ZANKE]
6. korak: IZHOD
Primer algoritma BFS
Zdaj pa na primeru razumejmo delovanje algoritma BFS. V spodnjem primeru je usmerjen graf s 7 vozlišči.
V zgornjem grafu je minimalno pot 'P' mogoče najti z uporabo BFS, ki se bo začela od vozlišča A in končala pri vozlišču E. Algoritem uporablja dve čakalni vrsti, in sicer QUEUE1 in QUEUE2. QUEUE1 vsebuje vsa vozlišča, ki jih je treba obdelati, medtem ko QUEUE2 vsebuje vsa vozlišča, ki so obdelana in izbrisana iz QUEUE1.
Zdaj pa začnimo preučevati graf, začenši z vozliščem A.
Korak 1 - Najprej dodajte A v čakalno vrsto1 in NULL v čakalno vrsto2.
QUEUE1 = {A} QUEUE2 = {NULL} 2. korak - Zdaj izbrišite vozlišče A iz čakalne vrste1 in ga dodajte v čakalno vrsto2. Vstavite vse sosede vozlišča A v čakalno vrsto1.
QUEUE1 = {B, D} QUEUE2 = {A} 3. korak - Zdaj izbrišite vozlišče B iz čakalne vrste1 in ga dodajte v čakalno vrsto2. Vstavite vse sosede vozlišča B v čakalno vrsto1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} 4. korak - Zdaj izbrišite vozlišče D iz čakalne vrste1 in ga dodajte v čakalno vrsto2. Vstavite vse sosede vozlišča D v čakalno vrsto1. Edini sosed vozlišča D je F, saj je že vstavljeno, zato ne bo ponovno vstavljeno.
java int za podvojitev
QUEUE1 = {C, F} QUEUE2 = {A, B, D} 5. korak - Izbrišite vozlišče C iz čakalne vrste1 in ga dodajte v čakalno vrsto2. Vstavite vse sosede vozlišča C v čakalno vrsto1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} 5. korak - Izbrišite vozlišče F iz čakalne vrste1 in ga dodajte v čakalno vrsto2. Vstavite vse sosede vozlišča F v čakalno vrsto1. Ker so vsi sosedi vozlišča F že prisotni, jih ne bomo znova vstavljali.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} 6. korak - Izbriši vozlišče E iz čakalne vrste1. Ker so vsi njegovi sosedi že dodani, jih ne bomo znova vstavljali. Zdaj so obiskana vsa vozlišča in ciljno vozlišče E se pojavi v čakalni vrsti2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Kompleksnost algoritma BFS
Časovna kompleksnost BFS je odvisna od podatkovne strukture, uporabljene za predstavitev grafa. Časovna kompleksnost algoritma BFS je O(V+E) , saj v najslabšem primeru algoritem BFS razišče vsako vozlišče in rob. V grafu je število vozlišč O(V), medtem ko je število robov O(E).
Prostorsko kompleksnost BFS lahko izrazimo kot O(V) , kjer je V število oglišč.
Implementacija algoritma BFS
Zdaj pa si oglejmo implementacijo algoritma BFS v Javi.
V tej kodi uporabljamo seznam sosednosti za predstavitev našega grafa. Implementacija algoritma iskanja najprej v širino v Javi olajša delo s seznamom sosednosti, saj moramo potovati po seznamu vozlišč, ki so pritrjena na vsako vozlišče šele, ko je vozlišče izključeno iz čakalne vrste na čelu (ali začetku) čakalne vrste.
kaj je obravnavanje izjem v Javi
V tem primeru je graf, ki ga uporabljamo za predstavitev kode, podan na naslednji način -
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;>