Prije nego što pogledamo razlike između BFS-a i DFS-a, prvo bismo trebali znati o BFS-u i DFS-u zasebno.
Što je BFS?
BFS stoji za Traži prvo u širinu . Također je poznat kao prolazak reda razine . Struktura podataka Queue koristi se za obilazak Breadth First Search. Kada koristimo BFS algoritam za obilazak u grafu, možemo smatrati bilo koji čvor korijenskim čvorom.
Razmotrimo donji grafikon za prvo pretraživanje u širinu.
veličine slova u lateksu
Pretpostavimo da čvor 0 smatramo korijenskim čvorom. Prema tome, prelazak bi započeo od čvora 0.
Nakon što se čvor 0 ukloni iz reda čekanja, on se ispisuje i označava kao a posjećeni čvor.
Nakon što se čvor 0 ukloni iz reda čekanja, tada će susjedni čvorovi čvora 0 biti umetnuti u red čekanja kao što je prikazano u nastavku:
Sada će čvor 1 biti uklonjen iz reda čekanja; ispisuje se i označava kao posjećeni čvor
Nakon što se čvor 1 ukloni iz reda čekanja, tada će svi susjedni čvorovi čvora 1 biti dodani u red čekanja. Susjedni čvorovi čvora 1 su 0, 3, 2, 6 i 5. Ali u red čekanja moramo umetnuti samo neposjećene čvorove. Budući da su čvorovi 3, 2, 6 i 5 neposjećeni; stoga će ovi čvorovi biti dodani u red čekanja kao što je prikazano u nastavku:
Sljedeći čvor je 3 u redu čekanja. Dakle, čvor 3 bit će uklonjen iz reda čekanja, bit će ispisan i označen kao posjećen kao što je prikazano u nastavku:
Nakon što se čvor 3 ukloni iz reda čekanja, tada će se svi susjedni čvorovi čvora 3 osim posjećenih čvorova dodati u red čekanja. Susjedni čvorovi čvora 3 su 0, 1, 2 i 4. Budući da su čvorovi 0, 1 već posjećeni, a čvor 2 je prisutan u redu čekanja; stoga moramo umetnuti samo čvor 4 u red čekanja.
python postavka staze
Sada, sljedeći čvor u redu čekanja je 2. Dakle, 2 će biti izbrisan iz reda čekanja. Ispisuje se i označava kao posjećeno kao što je prikazano u nastavku:
Nakon što se čvor 2 ukloni iz reda čekanja, tada će svi susjedni čvorovi čvora 2 osim posjećenih čvorova biti dodani u red čekanja. Susjedni čvorovi čvora 2 su 1, 3, 5, 6 i 4. Budući da su čvorovi 1 i 3 već posjećeni, a 4, 5, 6 su već dodani u red; dakle, ne trebamo umetnuti nijedan čvor u red čekanja.
Sljedeći element je 5. Dakle, 5 bi bio izbrisan iz reda čekanja. Ispisuje se i označava kao posjećeno kao što je prikazano u nastavku:
Nakon što se čvor 5 ukloni iz reda čekanja, tada će svi susjedni čvorovi čvora 5 osim posjećenih čvorova biti dodani u red čekanja. Susjedni čvorovi čvora 5 su 1 i 2. Budući da su oba čvora već posjećena; dakle, ne postoji vrh koji bi se umetnuo u red.
Sljedeći čvor je 6. Dakle, 6 će biti izbrisan iz reda čekanja. Ispisuje se i označava kao posjećeno kao što je prikazano u nastavku:
Nakon što se čvor 6 ukloni iz reda čekanja, tada će svi susjedni čvorovi čvora 6 osim posjećenih čvorova biti dodani u red čekanja. Susjedni čvorovi čvora 6 su 1 i 4. Budući da je čvor 1 već posjećen, a čvor 4 je već dodan u red; stoga ne postoji vrh koji bi se umetnuo u red.
Sljedeći element u redu je 4. Dakle, 4 će biti izbrisan iz reda. Ispisuje se i označava kao posjećeno.
Nakon što se čvor 4 ukloni iz reda čekanja, tada će svi susjedni čvorovi čvora 4 osim posjećenih čvorova biti dodani u red čekanja. Susjedni čvorovi čvora 4 su 3, 2 i 6. Budući da su svi susjedni čvorovi već posjećeni; tako da ne postoji vrh koji bi se umetnuo u red.
Što je DFS?
DFS označava Depth First Search. U DFS traversal-u koristi se struktura podataka stog koja radi na principu LIFO (Last In First Out). U DFS-u, prelaženje se može pokrenuti iz bilo kojeg čvora, ili možemo reći da se bilo koji čvor može smatrati korijenskim čvorom sve dok se korijenski čvor ne spomene u problemu.
U slučaju BFS-a, elementa koji se briše iz reda čekanja, susjedni čvorovi izbrisanog čvora dodaju se u red čekanja. Nasuprot tome, u DFS-u, element koji je uklonjen iz stoga, tada se u stog dodaje samo jedan susjedni čvor izbrisanog čvora.
Razmotrimo donji grafikon za obilazak pretraživanja prve dubine.
tok java filtera
Čvor 0 smatrajte korijenskim čvorom.
konstruktori u Javi
Prvo umećemo element 0 u stog kao što je prikazano u nastavku:
Čvor 0 ima dva susjedna čvora, tj. 1 i 3. Sada možemo uzeti samo jedan susjedni čvor, bilo 1 ili 3, za obilazak. Pretpostavimo da razmatramo čvor 1; stoga se 1 umeće u hrpu i ispisuje kao što je prikazano u nastavku:
Sada ćemo pogledati susjedne vrhove čvora 1. Neposjećeni susjedni vrhovi čvora 1 su 3, 2, 5 i 6. Možemo razmotriti bilo koji od ova četiri vrha. Pretpostavimo da uzmemo čvor 3 i umetnemo ga u stog kao što je prikazano u nastavku:
Razmotrimo neposjećene susjedne vrhove čvora 3. Neposjećene susjedne vrhove čvora 3 su 2 i 4. Možemo uzeti bilo koji od vrhova, tj. 2 ili 4. Pretpostavimo da uzmemo vrh 2 i umetnemo ga u hrpu kao što je prikazano u nastavku:
Neposjećeni susjedni vrhovi čvora 2 su 5 i 4. Možemo odabrati bilo koji od vrhova, tj. 5 ili 4. Pretpostavimo da uzmemo vrh 4 i umetnemo ga u hrpu kao što je prikazano u nastavku:
Sada ćemo razmotriti neposjećene susjedne vrhove čvora 4. Neposjećeni susjedni vrh čvora 4 je čvor 6. Stoga je element 6 umetnut u stog kao što je prikazano u nastavku:
Nakon umetanja elementa 6 u stog, pogledat ćemo neposjećene susjedne vrhove čvora 6. Kako nema neposjećenih susjednih vrhova čvora 6, tako da se ne možemo pomaknuti dalje od čvora 6. U ovom slučaju, izvršit ćemo vraćanje unatrag . Najviši element, tj. 6, iskočio bi iz hrpe kao što je prikazano u nastavku:
Najviši element u hrpi je 4. Budući da od čvora 4 nema neposjećenih susjednih vrhova; stoga je čvor 4 iskočio iz stoga kao što je prikazano u nastavku:
Sljedeći najviši element u stogu je 2. Sada ćemo pogledati neposjećene susjedne vrhove čvora 2. Budući da je ostao samo jedan neposjećeni čvor, tj. 5, čvor 5 bi bio gurnut u stog iznad 2 i ispisan kako je prikazano dolje:
Sada ćemo provjeriti susjedne vrhove čvora 5, koji su još neposjećeni. Budući da više nema vrha koji treba posjetiti, izbacujemo element 5 iz hrpe kao što je prikazano u nastavku:
Ne možemo se pomaknuti dalje 5, pa moramo izvršiti vraćanje unazad. U povratnom praćenju, najviši element bi iskočio iz hrpe. Najviši element je 5 koji bi iskočio iz hrpe, a mi se vraćamo na čvor 2 kao što je prikazano u nastavku:
python rstrip
Sada ćemo provjeriti neposjećene susjedne vrhove čvora 2. Kako više nema susjednih vrhova koje treba posjetiti, izvodimo praćenje unazad. U povratnom praćenju, najviši element, tj. 2, iskočio bi iz hrpe, a mi se vraćamo na čvor 3 kao što je prikazano u nastavku:
Sada ćemo provjeriti neposjećene susjedne vrhove čvora 3. Kako više nema susjednih vrhova koje treba posjetiti, izvodimo praćenje unatrag. U povratnom praćenju, najviši element, tj. 3, iskočio bi iz hrpe i vratili bismo se na čvor 1 kao što je prikazano u nastavku:
Nakon iskakanja elementa 3, provjerit ćemo neposjećene susjedne vrhove čvora 1. Budući da više nema vrha koji treba posjetiti; stoga će se izvršiti praćenje unatrag. U povratnom praćenju, najviši element, tj. 1 bi iskočio iz stoga, a mi se vraćamo na čvor 0 kao što je prikazano u nastavku:
Provjerit ćemo susjedne vrhove čvora 0, koji su još neposjećeni. Kako nema susjednog vrha koji treba posjetiti, izvodimo praćenje unatrag. U ovome bi samo jedan element, tj. 0 preostali u stogu, iskočio iz stoga kao što je prikazano u nastavku:
Kao što možemo vidjeti na gornjoj slici, stog je prazan. Dakle, ovdje moramo zaustaviti DFS obilazak, a elementi koji se ispisuju su rezultat DFS obilaska.
Razlike između BFS i DFS
Sljedeće su razlike između BFS i DFS:
| BFS | DFS | |
|---|---|---|
| Cijela forma | BFS je kratica za Breadth First Search. | DFS je kratica za Depth First Search. |
| Tehnika | To je tehnika temeljena na vrhovima za pronalaženje najkraće staze u grafu. | To je tehnika koja se temelji na rubovima jer se prvo istražuju vrhovi duž ruba od početnog do krajnjeg čvora. |
| Definicija | BFS je tehnika obilaska u kojoj se prvo istražuju svi čvorovi iste razine, a zatim se prelazi na sljedeću razinu. | DFS je također tehnika obilaska u kojoj se obilazak započinje od korijenskog čvora i istražuje čvorove što je dalje moguće dok ne dođemo do čvora koji nema neposjećene susjedne čvorove. |
| Struktura podataka | Struktura podataka reda čekanja koristi se za BFS obilazak. | Struktura podataka stog koristi se za BFS obilazak. |
| Vraćanje unatrag | BFS ne koristi koncept povratnog praćenja. | DFS koristi praćenje unatrag za prolazak kroz sve neposjećene čvorove. |
| Broj rubova | BFS pronalazi najkraći put koji ima minimalan broj bridova koje treba prijeći od izvorišta do odredišnog vrha. | U DFS-u je potreban veći broj bridova za prelazak od izvornog vrha do odredišnog vrha. |
| Optimalnost | BFS traversal je optimalan za one vrhove koji se traže bliže izvorišnom vrhu. | DFS traversal je optimalan za one grafove u kojima su rješenja udaljena od izvornog vrha. |
| Ubrzati | BFS je sporiji od DFS-a. | DFS je brži od BFS-a. |
| Prikladnost za stablo odlučivanja | Nije prikladan za stablo odlučivanja jer prvo zahtijeva istraživanje svih susjednih čvorova. | Pogodan je za stablo odlučivanja. Na temelju odluke istražuje sve staze. Kada je cilj pronađen, zaustavlja svoje obilaženje. |
| Učinkovita memorija | Nije memorijski učinkovit jer zahtijeva više memorije od DFS-a. | Memorijski je učinkovit jer zahtijeva manje memorije od BFS-a. |