Rozdiel medzi BFS a DFS

2019

Hlavným rozdielom medzi systémom BFS a systémom DFS je to, že služba BFS postupuje úrovňou podľa úrovní, zatiaľ čo služba DFS najprv vyberie cestu od začiatku ku koncovému uzlu (vertex), potom ďalšiu cestu od začiatku do konca a tak ďalej, až kým nebudú navštívené všetky uzly. Okrem toho BFS používa frontu na ukladanie uzlov, zatiaľ čo DFS používa zásobník na traverzovanie uzlov.

BFS a DFS sú metódy prechodu, ktoré sa používajú pri vyhľadávaní grafu. Priebeh grafu je proces návštevy všetkých uzlov grafu. Graf je skupina Vertices 'V' a Edges 'E', ktoré sa pripájajú k vrcholom.

Porovnávacia tabuľka

Základ pre porovnanie	BFS	DFS
základné	Algoritmus založený na vertexoch	Algoritmus založený na okrajoch
Štruktúra údajov používaná na ukladanie uzlov	fronta	Stoh
Spotreba pamäte	neefektívne	účinný
Štruktúra vytvoreného stromu	Široké a krátke	Úzke a dlhé
Traversing móda	Najskôr sa skúmajú najstaršie neviditeľné vrcholy.	Na začiatku sú preskúmané vrcholy pozdĺž okraja.
optimality	Optimálne na hľadanie najkratšej vzdialenosti, nie v cene.	Nie je optimálne
prihláška	Skúma bipartitný graf, pripojený komponent a najkratšiu cestu v grafe.	Skúma dva hrany pripojené graf, silne pripojený graf, acyklický graf a topologické poradie.

Definícia BFS

Najprv hľadanie šablóny (BFS) je metóda prechodu použitá v grafoch. Používa frontu na ukladanie navštívených vrcholov. V tejto metóde je dôraz kladený na vrcholy grafu, najprv je vybraný jeden vrchol, potom je navštívený a označený. Vrcholy susediace s navštíveným vrcholom sú potom navštívené a uložené vo fronte postupne. Podobne uložené vrcholy sa potom spracujú jeden po druhom a navštevujú sa ich susedné vrcholy. Uzol je podrobne preskúmaný pred návštevou akéhokoľvek iného uzla v grafe, inými slovami, najprv prechádza najprísnejšie nepreskúmané uzly.

príklad

Máme graf, ktorého vrcholy sú A, B, C, D, E, F, G. Vzhľadom na to, že A je východiskový bod. Kroky zahrnuté v tomto procese sú:

Vertex A je rozšírený a uložený vo fronte.
Vertices B, D a G nástupcov A sú rozšírené a uložené vo fronte zatiaľ čo Vertex A je odstránený.
Teraz B na prednom konci frontu je odstránený spolu s uložením jeho následných vrcholov E a F.
Vertex D na fronte frontu je odstránený a jeho pripojený uzol F je už navštívený.
Vertex G sa odstráni z fronty a má nástupcu E, ktorý už je navštívený.
Teraz E a F sú odstránené z fronty a jej nástupnícky vrchol C je preložený a uložený vo fronte.
Nakoniec C je tiež odstránená a fronta je prázdna, čo znamená, že sme hotoví.
Generovaný výstup je - A, B, D, G, E, F, C.

Aplikácie-

BFS môže byť užitočné pri zisťovaní, či má graf spojený komponent alebo nie. A tiež môže byť použitý pri detekcii bipartitného grafu .

Graf je bipartitný, keď sú vrcholy grafov rozdelené do dvoch disjunktných množín; žiadne dva susedné vrcholy by sa nenachádzali v tej istej sade. Ďalšou metódou kontroly bipartitného grafu je kontrola výskytu nepárneho cyklu v grafe. Bipartitný graf nesmie obsahovať nepárny cyklus.

BFS je tiež lepšie pri hľadaní najkratšej cesty v grafe môže byť považovaná za sieť.

Definícia DFS

Metóda presmerovania hĺbky prvého vyhľadávania (DFS) používa zásobník na uloženie navštívených vrcholov. DFS je metóda založená na okrajoch a pracuje rekurzívnym spôsobom, kde sú vrcholy preskúmané pozdĺž cesty (hrany). Prieskum uzla je pozastavený hneď, ako sa nájde ďalší nepreskúmaný uzol a najhlbšie nepreskúmané uzly sa prekonajú v popredí. DFS prejdite / navštívte každý vrchol presne raz a každý okraj sa kontroluje presne dvakrát.

príklad

Podobne ako v prípade BFS môžete použiť rovnaký graf na vykonávanie operácií DFS a príslušné kroky sú:

Vzhľadom na to, že A je východiskový vrchol, ktorý je skúmaný a uložený v zásobníku.
B nástupca vrcholu A je uložený v zásobníku.
Vertex B má dvoch nástupcov E a F, z ktorých je abecedne E najskôr preskúmaný a uložený v zásobníku.
Následník vertexu E, tj G je uložený v zásobníku.
Vertex G má dva navzájom spojené vrcholy a oba sú už navštívené, takže G je vyskočený zo stohu.
Podobne Es tiež odstránené.
Teraz, vrchol B je v hornej časti stohu, jeho ďalší uzol (vrchol) F je preskúmaný a uložený v zásobníku.
Vertex F má dve nástupky C a D, medzi ktorými je C najskôr prechádzajúce a uložené v zásobníku.
Vertex C má iba jedného predchodcu, ktorý je už navštívený, takže je odstránený zo stohu.
Teraz vertex D pripojený k F je navštívený a uložený v zásobníku.
Keďže vrchol D nemá žiadne neviditeľné uzly, D je odstránený.
Podobne F, B a A sú tiež vyskočené.
Generovaný výstup je - A, B, E, G, F, C, D.

aplikačne

Aplikácie systému DFS zahŕňajú kontrolu dvoch grafov pripojených na okraji, silne pripojeného grafu, acyklického grafu a topologického poradia .

Graf sa nazýva dva hrany pripojené, ak a len ak zostane pripojený, aj keď je jeden z jeho okrajov odstránený. Táto aplikácia je veľmi užitočná v počítačových sieťach, kde zlyhanie jedného odkazu v sieti neovplyvní zostávajúcu sieť a bude stále pripojené.

Silne pripojený graf je graf, v ktorom musí existovať cesta medzi usporiadanou dvojicou vrcholov. DFS sa používa v orientovanom grafe na vyhľadávanie cesty medzi každou usporiadanou dvojicou vrcholov. Služba DFS môže ľahko vyriešiť problémy s pripojením.

Kľúčové rozdiely medzi BFS a DFS

BFS je vertikálny algoritmus, zatiaľ čo DFS je algoritmus založený na okrajoch.
Štruktúra údajov o fronte sa používa v BFS. Na druhej strane DFS používa stoh alebo rekurziu.
Pamäťový priestor sa účinne využíva v systéme DFS, zatiaľ čo využitie priestoru v BFS nie je účinné.
BFS je optimálny algoritmus, zatiaľ čo DFS nie je optimálny.
DFS konštruuje úzke a dlhé stromy. Na rozdiel od toho BFS vytvára široký a krátky strom.

záver

BFS a DFS, oba metódy vyhľadávania grafov majú podobný čas prevádzky, ale rozdielna spotreba priestoru, DFS má lineárny priestor, pretože musíme pamätať jednu cestu s neprobádanými uzlami, zatiaľ čo BFS udržiava každý uzol v pamäti.

DFS prináša hlbšie riešenia a nie je optimálne, ale funguje dobre, keď je riešenie husté, zatiaľ čo BFS je optimálny, ktorý najskôr hľadá optimálny cieľ.