Razlika med BFS in DFS
Share
BFS proti DFS
Prvo iskanje širine (imenovano tudi BFS) je metoda iskanja, ki se uporablja za razširitev vseh vozlišč določenega grafa. To nalogo opravi z iskanjem vsake posamezne rešitve, da preuči in razširi ta vozlišča (ali kombinacijo zaporedja v njih). Kot tak BFS ne uporablja hevrističnega algoritma (ali algoritma, ki išče rešitev po več scenarijih). Ko dobimo vsa vozlišča, jih dodamo v čakalno vrsto, imenovano čakalna vrsta First In, First Out. Tista vozlišča, ki niso bila raziskana, so "shranjena" v posodi z oznako "odprto"; Ko so enkrat raziskani, se prevažajo v zabojniku z oznako "zaprto".
Globinsko prvo iskanje (znano tudi kot DFS) je metoda iskanja, ki se zakopava globlje v nadrejeno vozlišče iskanja, dokler cilj ni dosežen (ali dokler ni vozlišča brez drugih permutacij ali 'otrok'). Ko najdete en cilj, iskanje potegne nazaj na prejšnje vozlišče, ki je šlo z rešitvijo, ponavlja postopek, dokler niso bila vsa mesta uspešno uspešna. Tako vozlišča še naprej odlagajo za nadaljnje raziskovanje - temu pravimo nerekurzivna izvedba.
Značilnosti sistema BFS so prostorska in časovna zapletenost, popolnost, dokaz popolnosti in optimalnosti. Vesoljska zapletenost se nanaša na delež števila vozlišč na najgloblji ravni iskanja. Časovna zapletenost se nanaša na dejansko količino "časa", ki se porabi za preučitev vsake poti, ki jo vozlišče vodi v iskanju. Popolnost je v bistvu iskanje, ki najde rešitev v grafu ne glede na to, za kakšen graf gre. Dokaz popolnosti je najtanjša raven, na kateri se cilj najde v vozlišču v določeni globini. Končno, optimalnost se nanaša na BFS, ki ni tehtan - to je graf, uporabljen za stroške v enoti.
DFS je najbolj naraven rezultat z razteznim drevesom - to je drevo, sestavljeno iz vseh vrhov in nekaterih robov v usmerjenem grafu. V tej tvorbi je graf razdeljen na tri razrede: Naprej robove, ki kažejo od vozlišča do otroškega vozlišča; zadnji robovi, ki kažejo od vozlišča do prejšnjega vozlišča; in križnimi robovi, ki ne naredijo nobenega od teh.
Povzetek:
1. BFS išče vse rešitve v grafu, da razširi svoja vozlišča; DFS se zakopava globoko v otroškem vozlišču, dokler ni dosežen cilj.
2. Značilnosti sistema BFS so prostorska in časovna zapletenost, popolnost, dokaz popolnosti in optimalnosti; najbolj naraven rezultat za DFS je raztezno drevo s tremi razredi: sprednji robovi, zadnji robovi in križni robovi.
