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.
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.
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ľ.
