Iskanje v globino se običajno uporablja, ko morate preiskati celotno drevo. Lažje je implementirati (z uporabo rekurzije) kot BFS in zahteva manj stanja: medtem ko BFS zahteva, da shranite celotno 'mejo', DFS zahteva samo, da shranite seznam nadrejenih vozlišč trenutnega elementa.
Kdaj bi bil DFS boljši od BFS?
BFS je bolj primeren za iskanje po točkah, ki so bližje danemu viru. DFS je bolj primeren ko so rešitve stran od vira. 4. BFS najprej upošteva vse sosede in zato ni primeren za drevesa odločanja, ki se uporabljajo v igrah ali ugankah.
Za kaj se lahko uporablja DFS?
Aplikacije. Iskanje v globino se uporablja pri topološkem razvrščanju, težavah pri načrtovanju, zaznavanju ciklov v grafih in reševanju ugank z eno samo rešitvijo, kot je labirint ali uganka sudoku. Druge aplikacije vključujejo analizo omrežij, na primer testiranje, ali je graf dvodelen.
Kakšne so prednosti in slabosti DFS?
Če prečka pravo pot, bo dosegel ciljno vozlišče v krajšem časovnem obdobju kot BFS. Lahko najde rešitev, ne da bi preučil veliko iskanja, ker lahko dobimo želeno rešitev že na prvem mestu. Slabosti: Možno je, da se stanja ponavljajo.
Kakšna je prednost DFS pred BFS?
V bistvu bi šel po prvi poti in nikoli ne bi našel elementa. BFS bi sčasoma našelelement. Če je velikost grafa končna, bi DFS verjetno hitreje našel izstopajoči element (večja razdalja med korenom in ciljem), kjer bi BFS hitreje našel bližji element.
