Uvod u BFS algoritam
Za učinkovit pristup i upravljanje podacima, oni se mogu pohraniti i organizirati u posebnom formatu poznatom kao struktura podataka. Postoje mnoge strukture podataka kao što su stog, niz, vezani popis, redovi, drveće i grafikoni itd. U linearnim strukturama podataka, kao što su Stack, Array, Linked List i Queue, podaci su organizirani u linearnom redoslijedu, dok se u ne- linearne strukture podataka poput stabala i grafova, podaci su organizirani hijerarhijski ne u nizu. Graf je nelinearna struktura podataka koja ima čvorove i rubove. Čvorovi na grafikonu mogu se također nazvati vrhovima koji su konačnog broja i rubovi su povezujuće linije između bilo koja dva čvora.
U gornjem grafu vrhovi se mogu prikazati kao V = (A, B, C, D, E), a rubovi se mogu definirati kao
E = (AB, AC, CD, BE)
Što je BFS algoritam?
Obično postoje dva algoritma koja se koriste za pomicanje grafikona. To su BFS (prva širina pretraživanja) i DFS (Dubina prva pretraga) algoritmi. Obilazenje grafikona dolazi točno jednom po svakoj vrhovima ili čvoru i rubu, po dobro definiranom redoslijedu. Također, vrlo je važno pratiti one posjećene vrhove kako se dva puta ne bi prelazila ista vršica. U algoritmu prvog pretraživanja daha, putovanje započinje od odabranog čvora ili izvornog čvora, a prelazak se nastavlja preko čvorova koji su izravno povezani s izvornim čvorom. Jednostavnije rečeno, u BFS algoritmu treba prvo vodoravno pomicati i prelaziti trenutni sloj nakon čega treba preći na sljedeći sloj.
Kako djeluje algoritam BFS?
Uzmimo za primjer grafikona u nastavku.
Važni zadatak je pronaći najkraći put u grafikonu tijekom prolaska kroz čvorove. Kad prelazimo graf, verteks prelazi iz neotkrivenog u otkriveno stanje i konačno postaje potpuno otkriven. Treba napomenuti da je moguće zaglaviti se u nekom trenutku dok se kroz graf i čvor može posjetiti dvaput. Na taj način možemo upotrijebiti metodu označavanja čvorova nakon što promijeni stanje neotkrivanja do potpunog otkrivanja.
Na donjoj slici možemo vidjeti kako čvorovi mogu biti označeni na grafovima dok se u potpunosti otkrivaju označavajući ih crnom bojom. Moramo započeti na izvornom čvoru i kako prolazak napreduje kroz svaki čvor, oni mogu biti označeni kako bi se mogli prepoznati.
Okretanje polazi od verteksa, a zatim putuje do izlaznih rubova. Kad rub pređe u neotkrivenu kralježnicu, označava se kao otkriven. Ali kada rub pređe na potpuno otkrivenu ili otkrivenu granicu, to se ignorira.
Za usmjereni graf svaki se rub posjećuje jedanput, a za neusmjereni graf dvaput, jednom tijekom obilaska svakog čvora. Algoritam koji će se koristiti određuje se na temelju pohrane otkrivenih vrhova. U algoritmu BFS koristi se red gdje se prvo otkriva najstarija vrh, a zatim širi kroz slojeve iz početne vrhove.
Koraci se izvode za BFS algoritam
Niži koraci se izvode za BFS algoritam.
- U datom grafu počnimo s vršnog sloja, tj. Na gornjem dijagramu je to čvor 0. Razina u kojoj je prisutna ta vršina može se označiti kao sloj 0.
- Sljedeći je korak pronalaženje svih ostalih vrhova koji su susjedni početnoj vrhovi tj. Čvoru 0 ili su iz njega odmah dostupni. Tada možemo označiti ove susjedne vrhove da budu prisutni na sloju 1.
- Moguće je doći do iste vertexa zbog petlje u grafikonu. Dakle, trebali bismo putovati samo do onih vrhova koji bi trebali biti prisutni u istom sloju.
- Zatim je označena nadređena vrhova trenutačne kralježnice u kojoj se nalazimo. Isto se mora izvesti za sve vrhove na sloju 1.
- Zatim je sljedeći korak pronalaženje svih onih vrhova koji su samo jedan rub od svih vrhova koji su na Sloju 1. Ti će se novi vrhovi nalaziti na 2. sloju.
- Gornji postupak se ponavlja sve dok se ne završe svi čvorovi.
Primjer:
Uzmimo za primjer grafikona u nastavku i shvatimo kako funkcionira BFS algoritam. Općenito, u BFS algoritmu, red se koristi za red na čvorovima tijekom prolaska kroz čvorove.
U gornjem grafikonu prvo treba posjetiti čvor 0 i taj čvor je dodan u red donjem redu:
Nakon posjeta čvoru 0, susjedni čvorovi 0, 1 i 2 postavljaju se u red. Red čekanja može biti predstavljen na sljedeći način: 
Tada će se posjetiti prvi čvor u redu koji je 2. Nakon što je posjećen čvor 2, red čekanja može se predstaviti na sljedeći način:
Nakon posjeta čvoru 2, 5 će se staviti u red i budući da ne postoje neviđeni susjedni čvorovi za čvor 5, iako je 5 u redu, ali ga neće posjetiti dvaput.
Zatim je prvi čvor u redu čekanja 1 koji će biti posjećen. Susjedni čvorovi 3 i 4 postavljeni su u red. Red čekanja predstavljen je dolje
Dalje, prvi čvor u redu je 5, a za ovaj čvor nema više neviđenih susjednih čvorova. Isto vrijedi i za čvorove 3 i 4 za koja također nema više neviđenih susjednih čvorova.
Tako se prolaze svi čvorovi i na kraju, red postaje prazan.
Zaključak
Algoritam pretraživanja kruga nudi neke velike prednosti za preporučivanje. Jedna od mnogih primjena BFS algoritma je izračunavanje najkraćeg puta. Također, koristi se u umrežavanju kako bi se pronašli susjedni čvorovi i može se pronaći na web stranicama društvenih mreža, mrežnom prenosu i odvozu smeća. Korisnici moraju razumjeti zahtjev i obrazac podataka kako bi ih iskoristili za bolje performanse.
Preporučeni članci
Ovo je vodič za BFS algoritam. Ovdje smo raspravljali o konceptu, radu, koracima i primjeru performansi u BFS algoritmu. Možete i proći kroz naše druge Prijedloge članaka da biste saznali više -
- Što je pohlepni algoritam?
- Algoritam Ray Tracing
- Algoritam digitalnog potpisa
- Što je hibernacija Java?
- Kriptografija digitalnog potpisa
- BFS VS DFS | Top 6 razlike s Infografikom