U ovom ćemo članku raspravljati o BFS algoritmu u strukturi podataka. Pretraživanje u širinu algoritam je za obilazak grafa koji počinje obilaziti graf od korijenskog čvora i istražuje sve susjedne čvorove. Zatim odabire najbliži čvor i istražuje sve neistražene čvorove. Dok koristite BFS za obilazak, bilo koji čvor u grafu može se smatrati korijenskim čvorom.
Postoji mnogo načina za kretanje kroz graf, ali među njima je BFS pristup koji se najčešće koristi. To je rekurzivni algoritam za pretraživanje svih vrhova podatkovne strukture stabla ili grafa. BFS stavlja svaki vrh grafa u dvije kategorije - posjećene i neposjećene. Odabire jedan čvor u grafu i, nakon toga, posjećuje sve čvorove susjedne odabranom čvoru.
Primjene BFS algoritma
Primjene algoritma prvo u širinu dane su kako slijedi -
- BFS se može koristiti za pronalaženje susjednih lokacija iz dane izvorne lokacije.
- U peer-to-peer mreži, BFS algoritam se može koristiti kao metoda obilaženja za pronalaženje svih susjednih čvorova. Većina torrent klijenata, kao što su BitTorrent, uTorrent itd. koriste ovaj proces za pronalaženje 'seeds' i 'peers' u mreži.
- BFS se može koristiti u alatima za indeksiranje web stranica za izradu indeksa web stranica. To je jedan od glavnih algoritama koji se mogu koristiti za indeksiranje web stranica. Započinje kretanje od izvorne stranice i slijedi veze povezane sa stranicom. Ovdje se svaka web stranica smatra čvorom na grafikonu.
- BFS se koristi za određivanje najkraćeg puta i minimalnog razapinjućeg stabla.
- BFS se također koristi u Cheneyevoj tehnici za dupliciranje skupljanja smeća.
- Može se koristiti u ford-Fulkersonovoj metodi za izračunavanje maksimalnog protoka u mreži protoka.
Algoritam
Koraci uključeni u BFS algoritam za istraživanje grafa dani su kako slijedi -
Korak 1: SET STATUS = 1 (stanje spremno) za svaki čvor u G
Korak 2: Stavite početni čvor A u red i postavite mu STATUS = 2 (stanje čekanja)
Korak 3: Ponavljajte korake 4 i 5 dok QUEUE ne bude prazan
odabir više tablica sql
Korak 4: Uklonite čvor N iz reda čekanja. Obradite ga i postavite mu STATUS = 3 (obrađeno stanje).
Korak 5: Stavite u red sve susjede N koji su u stanju spremnosti (čiji STATUS = 1) i postavite
njihov STATUS = 2
(stanje čekanja)
kako mogu nadograditi java
[KRAJ PETLJE]
Korak 6: IZLAZ
Primjer BFS algoritma
Razmotrimo sada rad BFS algoritma pomoću primjera. U donjem primjeru postoji usmjereni graf koji ima 7 vrhova.
U gornjem grafikonu, minimalni put 'P' može se pronaći korištenjem BFS-a koji će započeti od čvora A i završiti u čvoru E. Algoritam koristi dva reda čekanja, naime QUEUE1 i QUEUE2. QUEUE1 sadrži sve čvorove koji se trebaju obraditi, dok QUEUE2 sadrži sve čvorove koji se obrađuju i brišu iz QUEUE1.
f-string python
Sada, počnimo ispitivati graf počevši od čvora A.
Korak 1 - Prvo dodajte A u queue1 i NULL u queue2.
QUEUE1 = {A} QUEUE2 = {NULL} Korak 2 - Sada izbrišite čvor A iz queue1 i dodajte ga u queue2. Umetnite sve susjede čvora A u red1.
QUEUE1 = {B, D} QUEUE2 = {A} 3. korak - Sada izbrišite čvor B iz queue1 i dodajte ga u queue2. Umetnite sve susjede čvora B u red1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Korak 4 - Sada izbrišite čvor D iz queue1 i dodajte ga u queue2. Umetnite sve susjede čvora D u red1. Jedini susjed čvora D je F budući da je već umetnut, tako da neće biti ponovno umetnut.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Korak 5 - Izbrišite čvor C iz queue1 i dodajte ga u queue2. Umetnite sve susjede čvora C u red1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Korak 5 - Izbrišite čvor F iz queue1 i dodajte ga u queue2. Umetnite sve susjede čvora F u red1. Budući da su svi susjedi čvora F već prisutni, nećemo ih ponovno umetati.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Korak 6 - Brisanje čvora E iz reda1. Budući da su svi njegovi susjedi već dodani, nećemo ih ponovno umetati. Sada su posjećeni svi čvorovi, a ciljni čvor E nailazi na queue2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Složenost BFS algoritma
Vremenska složenost BFS-a ovisi o strukturi podataka koja se koristi za predstavljanje grafa. Vremenska složenost BFS algoritma je O(V+E) , budući da u najgorem slučaju BFS algoritam istražuje svaki čvor i rub. U grafu je broj vrhova O(V), dok je broj bridova O(E).
Prostorna složenost BFS-a može se izraziti kao O(V) , gdje je V broj vrhova.
Implementacija BFS algoritma
Sada, da vidimo implementaciju BFS algoritma u Javi.
bourne-again školjka
U ovom kodu koristimo popis susjednosti za predstavljanje našeg grafa. Implementacija algoritma pretraživanja prvo u širinu u Javi čini mnogo lakšim rad s popisom susjedstva budući da moramo samo putovati kroz popis čvorova koji su pripojeni svakom čvoru nakon što se čvor skine s čela (ili početka) reda čekanja.
U ovom primjeru, grafikon koji koristimo za demonstraciju koda dan je kako slijedi -
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;>