BFS vs DFS – razlika između njih

Što je BFS?

BFS je algoritam koji se koristi za crtanje podataka ili pretraživanje stabla ili prelaž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) na grafu i zatim posjećuje sve čvorove koji su susjedni odabranom čvoru. Nakon što algoritam posjeti i označi početni čvor, tada se kreće prema najbližim neposjećenim čvorovima i analizira ih.

Nakon posjeta, svi čvorovi su označeni. Te se iteracije nastavljaju sve dok se svi čvorovi grafa uspješno ne posjete i ne obilježe. Potpuni oblik BFS-a je pretraživanje u širinu.

Što je DFS?

DFS je algoritam za pronalaženje ili prelaženje grafova ili stabala u smjeru dubine. Izvršenje algoritma počinje u korijenskom čvoru i istražuje svaku granu prije povratnog praćenja. Koristi podatkovnu strukturu hrpa za pamćenje, dobivanje sljedećeg vrha i pokretanje pretraživanja kad god se pojavi slijepa ulica u bilo kojoj iteraciji. Potpuni oblik DFS-a je pretraživanje prvo u dubinu.

Razlika između BFS i DFS binarnog stabla

Evo važnih razlika između BFS i DFS.

BFS	DFS
BFS pronalazi najkraći put do odredišta.	DFS ide na dno podstabla, a zatim se vraća unatrag.
Puni oblik BFS-a je Breadth-First Search.	Potpuni oblik DFS-a je pretraživanje prve dubine.
Koristi red čekanja za praćenje sljedeće lokacije koju treba posjetiti.	Koristi hrpu za praćenje sljedeće lokacije koju treba posjetiti.
BFS prolazi prema razini stabla.	DFS prelazi prema dubini stabla.
Implementiran je pomoću FIFO liste.	Implementira se pomoću LIFO liste.
Zahtijeva više memorije u usporedbi s DFS-om.	Zahtijeva manje memorije u usporedbi s BFS-om.
Ovaj algoritam daje rješenje najpliće staze.	Ovaj algoritam ne jamči rješenje najpliće staze.
Nema potrebe za vraćanjem unatrag u BFS-u.	U DFS-u postoji potreba za povratnim praćenjem.
Nikada ne možete biti zarobljeni u konačnim petljama.	Možete biti zarobljeni u beskonačnim petljama.
Ako ne pronađete nijedan cilj, možda ćete morati proširiti mnogo čvorova prije nego što se pronađe rješenje.	Ako ne pronađete nijedan cilj, može doći do povratnog praćenja lisnog čvora.

Primjer BFS-a

U sljedećem primjeru BFS-a koristili smo graf koji ima 6 vrhova.

Primjer BFS-a

Korak 1)

Imate graf od sedam brojeva u rasponu od 0 do 6.

Korak 2)

0 ili nula je označen kao korijenski čvor.

Korak 3)

0 se posjećuje, označava i umeće u podatkovnu strukturu reda.

Korak 4)

Preostalih 0 susjednih i neposjećenih čvorova se posjećuju, označavaju i umeću u red čekanja.

Korak 5)

Iteracije obilaska se ponavljaju 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)

Počeli smo od vrha 0. Algoritam počinje stavljanjem istog na popis posjećenih i istovremeno stavljanjem svih njegovih susjednih vrhova u struktura podataka nazvan stog.

Korak 2)

Posjetit ćete element koji je na vrhu hrpe, 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 neposjećeni obližnji vrh u 4. Stoga ga dodajemo u hrpu i posjećujemo ga.

Korak 4)

Konačno, posjetit ćemo posljednji vrh 3, on nema neposjećenih susjednih čvorova. Završili smo obilazak grafa pomoću DFS algoritma.

Primjene BFS-a

Ovdje su aplikacije BFS-a:

Neponderirani grafikoni

BFS algoritam može lako stvoriti najkraći put i minimalno razapinjuće stablo za posjet svim vrhovima grafa u najkraćem mogućem vremenu s visokom točnošć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 indeksi

Tražilice ili alati za indeksiranje weba mogu lako izgraditi više razina indeksa korištenjem BFS-a. Implementacija BFS-a počinje od izvora, a to je web stranica, a zatim posjećuje sve poveznice s tog izvora.

Mrežno emitiranje

Emitirani paket je vođen BFS algoritmom da pronađe i dosegne sve čvorove za koje ima adresu.

Primjene DFS-a

Ovdje su važne primjene DFS-a:

Ponderirani grafikon

U ponderiranom grafu, obilazak DFS grafa generira stablo najkraće staze i minimalno razapinjuće stablo.

Detektiranje ciklusa u grafu

Graf ima ciklus ako smo pronašli stražnji rub tijekom DFS-a. Stoga bismo trebali pokrenuti DFS za graf i provjeriti stražnje rubove.

Pronalaženje puta

Možemo se specijalizirati za DFS algoritam za pretraživanje staze između dva vrha.

Topološko sortiranje

Prvenstveno se koristi za raspoređivanje poslova iz zadanih ovisnosti među grupom poslova. U informatici se koristi u raspoređivanju instrukcija, serijalizaciji podataka, logičkoj sintezi, određivanju redoslijeda zadataka kompilacije.

Pretraživanje jako povezanih komponenti grafa

Koristi se u DFS grafu kada postoji put od svakog pojedinog vrha u grafu do ostalih preostalih vrhova.

Rješavanje zagonetki sa samo jednim rješenjem

DFS algoritam može se lako prilagoditi za pretraživanje svih rješenja labirinta uključivanjem čvorova na postojećoj stazi u posjećenom skupu.