Razlika između BFS VS DFS

Prvo pretraživanje širine (BFS) i prvo pretraživanje dubine (DFS) dva su važna algoritma koja se koriste za pretraživanje. Prvo pretraživanje širine započinje pretraživanje s prvog čvora, a zatim se kreće kroz razine koje su bliže korijenskom čvoru, dok algoritam Dubine prve pretrage započinje s prvim čvorom, a zatim dovršava svoj put do krajnjeg čvora odgovarajuće staze. Oba algoritma tijekom pretraživanja prolaze kroz svaki čvor. Za dva su algoritma napisani različiti kodovi za izvršavanje procesa vožnje. Oni se također smatraju važnim algoritmima pretraživanja u umjetnoj inteligenciji.

U ovoj ćemo temi saznati više o BFS VS DFS.

Kako funkcioniraju BFS i DFS?

Mehanizam rada oba algoritma opisan je u nastavku s primjerima. Molimo da ih potražite radi boljeg razumijevanja korištenog pristupa.

Primjer prvog pretraživanja širine

  • Korak 1: N1 je korijenski čvor, pa će započeti odavde. N1 je povezan s tri čvora N2, N3 i N4. Sva tri čvora još nisu posjećena. Dakle, krećemo od N2 i spremamo ga u red. Dakle, red pod nazivom Q sadrži samo N2.

P: N2

  • Korak 2: Slijedeći čvor koji je spojen na N1 je N3. Budući da smo prešli ili posjetili čvor spremit ćemo ga u red. Dakle, ažurirani red je

P: N3, N2

  • Korak 3: Sljedeći čvor koji je povezan s korijenskim čvorom je N4. Spremit ćemo ga u red.

P: N4, N3, N2

  • Korak 4: Svi čvorovi koji su spojeni na N1 spremaju se u red. Sada uklanjamo N2 iz reda čekanja po principu First in First Out (FIFO) i pronalazimo čvorove koji su spojeni na N2, tj. N5. N5 nije posjećen jednom, pa ćemo ga spremiti u red.

P: N5, N4, N3

  • Korak 5: Sve su vertikale posjećene, pa nastavljamo uklanjati čvorove iz reda dok ne bude prazan.

Primjer prvog pretraživanja dubine

  • Korak 1: Počet ćemo s N1 kao početnim čvorom i spremiti ga u hrpu S. N1 je povezan s tri susjedna čvora N2, N3 i N4. Počevši od N2 (možete početi abecednim ili brojevnim brojem), to ćemo staviti u stog.

S: N2 (odozgo), N1

  • Korak 2: Sada su susjedni čvorovi N2 N1 i N5. Budući da je N1 već prisutan u hrpi, što znači da je posjećen, pa ćemo uzeti N5 i staviti ga u hrpu S.

S: N5 (odozgo), N2, N1

  • Korak 3: Sada su susjedni čvorovi N5 N3 i N4. Mi započinjemo s N3 i stavljamo je u hrpu.

S: N3 (odozgo), N5, N2, N1

Sada je N3 povezan s N5 i N1 koji su već prisutni u snopu što znači da su posjećeni, pa ćemo ukloniti N3 iz snopa prema principu Last in First Out (LIFO).

S: N5 (odozgo), N2, N1

  • Korak 4: Sada ćemo staviti posljednji čvor, na koji nismo naišli u čitavom prelasku N4 i staviti ga u hrpu.

S: N4 (odozgo), N5, N2, N1

  • Korak 5: Sada nismo izostavljeni s bilo kojim drugim čvorovima, pa ćemo provjeriti u snopu postoje li čvorovi povezani s odgovarajućim čvorovima u njemu koji nisu posjećeni. Ako su posjećeni svi povezani čvorovi, uklonit ćemo čvorove koji su prisutni u hrpi. Na primjer, N4 nema spojne čvorove koje nismo provjerili pa ćemo ih ukloniti iz snopa. Slično tome, možemo provjeriti i za druge čvorove. Algoritam se zaustavlja nakon što je snop prazan.

Usporedba između BFS VS DFS (Infographics)

Ispod je top 6 razlike između BFS VS DFS

Ključne razlike između BFS i DFS

Razgovarajte o nekim glavnim ključnim razlikama između BFS-a i DFS-a

  • Prvo pretraživanje širine (BFS) počinje od korijenskog čvora i posjećuje sve dotične čvorove na njemu, dok DFS započinje s korijenskim čvorom i završava puni put vezan uz čvor.
  • BFS slijedi pristup čekanja dok DFS slijedi pristup Stacka.
  • Pristup koji se koristi u BFS-u je optimalan, dok postupak koji se koristi u DFS-u nije optimalan.
  • Ako je naš cilj pronaći najkraći put, preferira se BFS nad DFS-om.

Usporedna tablica BFS-a i DFS-a

Razmotrimo gornju usporedbu između BFS-a i DFS-a

BFSDFS
Potpuni oblik BFS-a je Breadth-First Search.Potpuni oblik DFS-a je Dubinska prva pretraga
BFS je namijenjen pronalasku najkraće udaljenosti i kreće se od prvog ili korijenskog čvora i kreće se kroz sve čvorove vezane uz odgovarajuće čvorove. Nakon što prođete u nastavku primjera, možete dobiti jasan uvid u njegov radni mehanizam.DFS slijedi pristup temeljen na dubini i on završava puni put kroz sve čvorove pričvršćene na odnosni čvor. Nakon što prođete u nastavku primjera, možete dobiti jasan uvid u njegov radni mehanizam.
Izvodi se pomoću principa čekanja, što je pristup First In First Out (FIFO).To se provodi po principu Stack, što je pristup Last In First out (LIFO).
Čvorovi koji su prolazili više puta uklanjaju se iz reda čekanja.Posjećeni čvorovi ubacuju se u snop, a kasnije, ako više nema čvorova koji se posjećuju, uklanjaju se.
To je relativno sporije od prvog pretraživanja po dubini.Brži je od algoritma Breadth-First Search.
Dodjela memorije veća je od algoritma Dubine prvog pretraživanja.Raspodjela memorije je usporedno manja od algoritma Breadth-First Search

Zaključak

Postoje mnoge aplikacije u kojima se gornji algoritmi koriste kao strojno učenje ili za pronalaženje rješenja vezanih uz umjetnu inteligenciju itd. Koriste se uglavnom u grafovima kako bi se utvrdilo je li dvostrano ili ne, za otkrivanje povezanih ciklusa ili komponenti. Oni se također smatraju važnim algoritmima za pronalaženje puta ili za pronalazak najkraće udaljenosti. Ovisno o zahtjevima tvrtke, možemo koristiti dva algoritma. Ipak, pretraga s prvom krugom smatra se optimalnim načinom nego algoritmom Dubine prve pretrage.

Preporučeni članci

Ovo je vodič za BFS VS DFS. Ovdje smo raspravljali o BFS VS DFS ključne razlike s infografikom i tablicom usporedbe. Možete također pogledati sljedeće članke da biste saznali više -

  1. BFS algoritam
  2. TeraData vs Oracle
  3. Big Data vs Data Warehouse
  4. Veliki podaci vs Apache Hadoop: Usporedba najboljih 4 koje morate naučiti

Kategorija:

Razvoj softvera