Što je BFS?
BFS je algoritam koji se koristi za grafički prikaz podataka ili pretraživanje stabla ili obilaženje struktura. Algoritam učinkovito posjećuje i označava sve ključne čvorove u grafikonu na precizan način.
Ovaj algoritam odabire jedan čvor (početnu ili izvornu točku) u grafikonu, a zatim posjećuje sve čvorove susjedne odabranom čvoru. Jednom kada algoritam posjeti i označi početni čvor, tada se kreće prema najbližim ne posjećenim čvorovima i analizira ih.
Jednom posjećeni svi čvorovi su označeni. Te se ponavljanja nastavljaju sve dok svi čvorovi grafikona nisu uspješno posjećeni i označeni. Cjeloviti oblik BFS-a je pretraga koja je prva širina.
U ovom BSF vs. DFS Binarno stablo tutorial, naučit ćete:
- Što je BFS?
- Što je DFS?
- Primjer BFS-a
- Primjer DFS-a
- Razlika između BFS i DFS binarnog stabla
- Primjene BFS-a
- Primjene DFS-a
Što je DFS?
DFS je algoritam za pronalaženje ili prelazak grafova ili stabala u smjeru dubine. Izvršenje algoritma započinje na korijenskom čvoru i istražuje svaku granu prije povratka unatrag. Koristi strukturu podataka snopa za pamćenje, dobivanje sljedećeg vrha i započinjanje pretraživanja, kad god se u bilo kojoj iteraciji pojavi slijepa ulica. Puni oblik DFS-a je pretraga po dubini.
Primjer BFS-a
U sljedećem primjeru DFS-a koristili smo graf koji ima 6 vrhova.
Primjer BFS-a
Korak 1)
Imate grafikon od sedam brojeva u rasponu od 0 - 6.
Korak 2)
0 ili nula označena je kao korijenski čvor.
Korak 3)
0 je posjećeno, označeno i umetnuto u strukturu podataka o redu čekanja.
Korak 4)
Preostalih 0 susjednih i ne posjećenih čvorova posjećuju se, označavaju i ubacuju u red čekanja.
Korak 5)
Iteracije prelaska ponavljaju se dok se ne posjete svi čvorovi.
Primjer DFS-a
U sljedećem primjeru DFS-a koristili smo neusmjereni graf koji ima 5 vrhova.
Korak 1)
Krenuli smo od vrha 0. Algoritam započinje stavljanjem na posjećeni popis i istovremeno stavljanjem svih njegovih susjednih vrhova u strukturu podataka koja se naziva stog.
Korak 2)
Posjetit ćete element koji se nalazi na vrhu stoga, na primjer 1, i otići do njegovih susjednih čvorova. To je zato što je 0 već posjećeno. Stoga posjećujemo vrh 2.
Korak 3)
Vrh 2 ima ne posjećeni obližnji vrh u 4. Stoga ga dodajemo u skup i posjećujemo.
Korak 4)
Konačno, posjetit ćemo posljednji vrh 3, on nema nijedan neposjećeni susjedni čvor. Završili smo zaokret grafa pomoću algoritma DFS.
Razlika između BFS i DFS binarnog stabla
| BFS | DFS |
| BFS pronalazi najkraći put do odredišta. | DFS ide na dno podstabla, a zatim se vraća. |
| Puni oblik BFS-a je pretraživanje od prve širine. | Puni oblik DFS-a je Dubinsko prvo pretraživanje. |
| Koristi red za bilježenje sljedeće lokacije koju treba posjetiti. | Koristi snop za praćenje sljedećeg mjesta koje treba posjetiti. |
| BFS prolazi kroz razinu stabla. | DFS prelazi prema dubini stabla. |
| Provodi se pomoću FIFO popisa. | Provodi se pomoću LIFO popisa. |
| Zahtijeva više memorije u usporedbi s DFS-om. | Zahtijeva manje memorije u usporedbi s BFS-om. |
| Ovaj algoritam daje rješenje s najplićom stazom. | Ovaj algoritam ne garantira rješenje s najplićom stazom. |
| U BFS-u nije potrebno vraćanje unatrag. | U DFS-u postoji potreba za povratom unatrag. |
| Nikada ne možete biti zarobljeni u konačne petlje. | Možete biti zarobljeni u beskonačne petlje. |
| Ako ne pronađete nikakav cilj, možda ćete trebati proširiti mnogo čvorova prije nego što se rješenje pronađe. | Ako ne pronađete nikakav cilj, može se dogoditi povrat unatrag lisnih čvorova. |
Primjene BFS-a
Evo aplikacija BFS-a:
Neponderirani grafikoni:
BFS algoritam može lako stvoriti najkraći put i minimalno rasponično stablo za posjećivanje svih vrhova grafa u najkraćem mogućem roku s velikom preciznošću.
P2P mreže:
BFS se može implementirati za lociranje svih najbližih ili susjednih čvorova u peer to peer mreži. Tako ćete brže pronaći potrebne podatke.
Web alati za indeksiranje:
Tražilice ili alati za indeksiranje weba mogu jednostavno izgraditi više razina indeksa koristeći BFS. Implementacija BFS-a započinje od izvora, a to je web stranica, a zatim posjećuje sve veze s tog izvora.
Mrežno emitiranje:
Emitirani paket vođen je BFS algoritmom kako bi pronašao i došao do svih čvorova kojima ima adresu.
Primjene DFS-a
Evo važnih aplikacija DFS-a:
Ponderirani grafikon:
U ponderiranom grafu, DFS prelazak grafa generira stablo najkraće staze i minimalno rasponično stablo.
Otkrivanje ciklusa u grafikonu:
Grafikon ima ciklus ako smo pronašli stražnji rub tijekom DFS-a. Stoga bismo trebali pokrenuti DFS za graf i provjeriti za stražnje rubove.
Traženje puta:
Možemo se specijalizirati za algoritam DFS za traženje puta između dva vrha.
Topološko sortiranje:
To se prvenstveno koristi za raspoređivanje radnih mjesta od ponuđenih ovisnosti među skupinu poslova. U računalnoj znanosti koristi se u raspoređivanju instrukcija, serializaciji podataka, sintezi logike, određivanju redoslijeda zadataka kompilacije.
Traženje čvrsto povezanih komponenata grafa:
Upotrebljava se u DFS grafu kada postoji put od svakog vrha u grafu do ostalih preostalih vrhova.
Rješavanje zagonetki samo jednim rješenjem:
DFS algoritam može se lako prilagoditi pretraživanju svih rješenja labirinta uključivanjem čvorova na postojeću stazu u posjećeni skup.
KLJUČNE RAZLIKE:
- BFS pronalazi najkraći put do odredišta, dok DFS ide na dno podstabla, a zatim se vraća.
- Puni oblik BFS-a je pretraživanje širine prve, dok je puni oblik DFS-a dubinsko pretraživanje.
- BFS koristi red za praćenje sljedećeg mjesta koje treba posjetiti. dok DFS koristi stog za praćenje sljedećeg mjesta koje treba posjetiti.
- BFS prolazi prema razini stabla, dok DFS prolazi prema dubini stabla.
- BFS se implementira pomoću FIFO liste, s druge strane DFS se primjenjuje pomoću LIFO liste.
- U BFS-u nikada ne možete biti zarobljeni u konačne petlje, dok u DFS-u možete biti zarobljeni u beskonačne petlje.