Rozdiel medzi BFS a DFS

BFS vs DFS

Prvé vyhľadávanie šírky (známe tiež ako BFS) je metóda vyhľadávania používaná na rozšírenie všetkých uzlov konkrétneho grafu. Túto úlohu plní hľadaním každého jednotlivého riešenia, aby sa preskúmali a rozšírili tieto uzly (alebo kombinácia sekvencií v nich). Ako taký BFS nepoužíva heuristický algoritmus (alebo algoritmus, ktorý hľadá riešenie prostredníctvom viacerých scenárov). Po získaní všetkých uzlov sa tieto spoja do frontu známeho ako front First In, First Out. Uzly, ktoré neboli preskúmané, sú „uložené“ v kontajneri označenom „otvorené“; po preskúmaní sa prepravia do kontajnera označeného „zatvorené“.

Hĺbkové prvé vyhľadávanie (známe aj ako DFS) je metóda vyhľadávania, ktorá sa prehĺbi hlbšie do podriadeného uzla vyhľadávania, až kým sa nedosiahne cieľ (alebo kým sa nedosiahne uzol bez akýchkoľvek ďalších permutácií alebo „detí“). Po nájdení jedného cieľa sa vyhľadávanie vráti k predchádzajúcemu uzlu, ktorý prešiel s riešením, a tento proces sa opakuje, až kým sa všetky uzly úspešne neprehľadajú. Uzly sú preto naďalej vyhradené na ďalšie skúmanie - nazýva sa to nerekurzívna implementácia.

Medzi vlastnosti BFS patrí zložitosť priestoru a času, úplnosť, dôkaz úplnosti a optimálnosť. Zložitosť priestoru predstavuje podiel počtu uzlov na najhlbšej úrovni vyhľadávania. Časová zložitosť sa týka skutočného množstva „času“ použitého na zváženie každej cesty, ktorú uzol vykoná pri vyhľadávaní. Úplnosť je v podstate vyhľadávanie, ktoré nájde riešenie v grafe bez ohľadu na to, aký je to graf. Dôkazom úplnosti je najhlbšia úroveň, na ktorej sa nachádza cieľ v uzle v určitej hĺbke. Nakoniec, optimálnosť sa vzťahuje na BFS, ktorý nie je vážený - to je graf používaný pre náklady na jednotku kroku.

DFS je najprirodzenejší výstup využívajúci preklenovací strom - strom tvorený všetkými vrcholmi a niektorými okrajmi v nepriamom grafe. V tejto zostave je graf rozdelený do troch tried: Predné hrany, smerujúce z uzla na podradený uzol; zadné hrany smerujúce z uzla na predchádzajúci uzol; a priečne hrany, ktoré nerobia ani jeden z nich.

Zhrnutie:

1. BFS prehľadáva každé jednotlivé riešenie v grafe a rozširuje svoje uzly; DFS sa prehrabáva hlboko v detskom uzle, kým sa nedosiahne cieľ.

2. Charakteristikou BFS je priestorová a časová zložitosť, úplnosť, dôkaz úplnosti a optimálnosť; najprirodzenejším výstupom pre DFS je preklenovací strom s tromi triedami: predné hrany, zadné hrany a priečne hrany.