hlavní rozdíl mezi BFS a DFS je, že BFS výnosů úroveň podle úrovně, zatímco DFS následuje první cestu tvoří začíná na koncový uzel (vertex), pak další cesta od začátku do konce, a tak dále, dokud všechny uzly jsou navštěvovány. Kromě toho BFS používá frontu pro ukládání uzlů, zatímco DFS používá zásobník pro průchod uzlů.
BFS a DFS jsou metody procházení používané při hledání grafu. Graph traversal je proces návštěvy všech uzlů grafu. Graf je skupina vrcholů “ V „a hran“ E “ spojujících se s vrcholy.
obsah: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure z konstruovaného stromu | široký a krátký | úzký a dlouhý |
| jsou nejprve prozkoumány nejstarší nenavštívené vrcholy. | vrcholy podél okraje jsou prozkoumány na začátku. | |
| optimalita | optimální pro nalezení nejkratší vzdálenosti, nikoli v ceně. | Ne optimální |
| Použití | Zkoumá bipartitní graf, připojené komponenty a nejkratší cestu přítomen v grafu. | zkoumá dvouhranně připojený graf, silně propojený graf, acyklický graf a topologické pořadí. |
Definice BFS
Šířka First Search (BFS) je křížení metody použité v grafech. Používá frontu pro ukládání navštívených vrcholů. V této metodě je důraz kladen na vrcholy grafu, nejprve je vybrán jeden vrchol, poté je navštíven a označen. Vrcholy sousedící s navštíveným vrcholem jsou pak navštíveny a uloženy ve frontě postupně.
podobně jsou uložené vrcholy ošetřeny jeden po druhém a jejich sousední vrcholy jsou navštíveny. Uzel je plně prozkoumány před návštěvou libovolného uzlu v grafu, jinými slovy, to prochází nejmírnější neprozkoumané uzly první.
Příklad:
Máme graf, jehož vrcholy jsou A, B, C, D, E, F, G úvahu jako výchozí bod. Kroky zapojené do procesu jsou:
- Vertex a je rozšířen a uložen ve frontě.
- vrcholy B, D A G nástupci A, jsou rozšířeny a uloženy ve frontě mezitím vrchol a odstraněn.
- nyní je B na předním konci fronty odstraněn spolu s uložením jeho nástupnických vrcholů E A F.
- Vertex D je na předním konci fronty je odstraněn a jeho připojený uzel F je již navštíven.
- Vertex G je odstraněn z fronty a má nástupce E, který je již navštíven.
- nyní jsou E A F odstraněny z fronty a jeho nástupce vertex C je procházen a uložen ve frontě.
- konečně C je také odstraněn a fronta je prázdná, což znamená, že jsme hotovi.
- generovaný výstup je – A, B, D, G, E, F, C.
Aplikace
BFS mohou být užitečné při hledání, zda graf má připojené komponenty, nebo ne. A také může být použit při detekci bipartitního grafu.
graf je bipartitní, když graf vrcholy jsou rozdělené na dvě disjunktní množiny; žádné dva sousední vrcholy bude bydlet ve stejném souboru. Další metodou kontroly bipartitního grafu je kontrola výskytu lichého cyklu v grafu. Bipartitní graf nesmí obsahovat lichý cyklus.
BFS je také lepší při hledání nejkratší cesty v grafu, kterou lze považovat za síť.
definice DFS
Depth First Search (DFS) traversing method používá zásobník pro ukládání navštívených vrcholů. DFS je metoda založená na hraně a pracuje rekurzivním způsobem, kde jsou vrcholy prozkoumány podél cesty (hrany). Průzkum uzlu je pozastaven, jakmile je nalezen další neprozkoumaný uzel a nejhlubší neprozkoumané uzly jsou překonány především. DFS traverse / navštivte každý vrchol přesně jednou a každá hrana je kontrolována přesně dvakrát.
příklad
podobný BFS umožňuje stejný graf pro provádění operací DFS a příslušné kroky jsou:
- s ohledem na a jako výchozí vrchol, který je prozkoumán a uložen v zásobníku.
- b nástupce vrchol A je uložen v zásobníku.
- Vertex B má dva nástupce E A F, mezi nimi abecedně E je nejprve prozkoumán a uložen v zásobníku.
- nástupce vertexu E, tj. G je uložen v zásobníku.
- Vertex G má dva připojené vrcholy a oba jsou již navštíveny, takže G je vyskočeno ze zásobníku.
- podobně, E s také odstraněny.
- nyní je vrchol B v horní části zásobníku, jeho další uzel(vrchol) F je prozkoumán a uložen v zásobníku.
- Vertex F má dva nástupce C A D, mezi nimi C je nejprve projet a uložen v zásobníku.
- Vertex C má pouze jednoho předchůdce, který je již navštíven, takže je odstraněn ze zásobníku.
- nyní vertex D připojený k F je navštíven a uložen v zásobníku.
- protože vertex D nemá žádné nenavštívené uzly, proto je D odstraněn.
- podobně jsou také vyskočeny F, B A A.
- generovaný výstup je – A, B, E, G, F, C, D.
Aplikace
aplikace DFS zahrnuje kontrolu dvě hrany souvislého grafu, pevně připojený graf, acyklický graf a topologické pořadí.
graf se nazývá dvě hrany připojené pouze tehdy, pokud zůstane připojen, i když je jeden z jeho okrajů odstraněn. Tato aplikace je velmi užitečná v počítačových sítích, kde selhání jednoho odkazu v síti neovlivní zbývající síť a bude stále připojeno.
Silně souvislého grafu je graf, ve kterém musí existovat cesta mezi nařízeno dvojice vrcholů. DFS se používá v orientovaném grafu pro vyhledávání cesty mezi každou uspořádanou dvojicí vrcholů. DFS může snadno vyřešit problémy s připojením.
klíčové rozdíly mezi BFS a DFS
- BFS je algoritmus založený na vertexu, zatímco DFS je algoritmus založený na hraně.
- datová struktura fronty se používá v BFS. Na druhou stranu, DFS používá zásobník nebo rekurzi.
- paměťový prostor je efektivně využíván v DFS, zatímco využití prostoru v BFS není efektivní.
- BFS je optimální algoritmus, zatímco DFS není optimální.
- DFS vytváří úzké a dlouhé stromy. Proti, BFS konstruuje široký a krátký strom.
Závěr
BFS a DFS, a to jak z grafu, hledání techniky mají podobné běží čas, ale jiný prostor, spotřeba, DFS trvá lineárního prostoru, protože musíme mít na paměti jednu cestu s neprozkoumané uzly, zatímco BFS udržuje každý uzel v paměti.
DFS poskytuje hlubší řešení a není optimální, ale funguje dobře, když je řešení husté, zatímco BFS je optimální, který nejprve hledá optimální cíl.