Doporučená, 2021

Redakce Choice

Rozdíl mezi BFS a DFS

Hlavní rozdíl mezi BFS a DFS spočívá v tom, že BFS postupuje na úrovni podle úrovně, zatímco DFS následuje nejprve cestu od počátečního do koncového uzlu (vertex), pak další cestu od začátku do konce a tak dále, dokud nejsou navštíveny všechny uzly. Navíc BFS používá frontu pro ukládání uzlů, zatímco DFS používá zásobník pro přechod uzlů.

BFS a DFS jsou metody procházení používané při hledání grafu. Přechod grafu je proces návštěvy všech uzlů grafu. Graf je skupina Vertices 'V' a Edges 'E' připojující se k vrcholům.

Srovnávací graf

Základ pro srovnání
BFSDFS
ZákladníVertexový algoritmusAlgoritmus založený na hraně
Datová struktura pro uložení uzlůFrontaZásobník
Spotřeba pamětiNeefektivníÚčinný
Struktura konstruovaného stromuŠiroké a krátkéÚzké a dlouhé
Traversing módaNejdříve jsou prozkoumány nejstarší neviděné vrcholy.Na začátku se zkoumají svislé hrany.
OptimalityOptimální pro nalezení nejkratší vzdálenosti, ne v nákladech.Není optimální
aplikaceZkoumá bipartitní graf, připojenou komponentu a nejkratší cestu v grafu.Zkoumá dvouhranný připojený graf, silně propojený graf, acyklický graf a topologický řád.

Definice BFS

Breadth First Search (BFS) je metoda procházení 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, pak je navštíven a označen. Vrcholy sousedící s navštíveným vrcholem jsou pak postupně sledovány a uloženy ve frontě. Podobně jsou uložené vrcholy zpracovány jeden po druhém a jejich sousední vrcholy jsou navštíveny. Uzel je plně prozkoumán před návštěvou jakéhokoli jiného uzlu v grafu, jinými slovy, nejprve přejíždí nejmenší neprozkoumané uzly.

Příklad

Máme graf, jehož vrcholy jsou A, B, C, D, E, F, G. Zvažujeme A jako výchozí bod. Kroky tohoto procesu jsou:

  • Vertex A je rozšířen a uložen ve frontě.
  • Vertikály B, D a G nástupců A, jsou mezitím rozšířeny a uloženy do fronty Vertex A odstraněny.
  • Nyní je B na předním konci fronty odstraněn spolu s uložením jeho následných vrcholů E a F.
  • Vrchol D je na předním konci fronty 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.
  • E a F jsou nyní odstraněny z fronty a jejich nástupní vertex C je uložen ve frontě.
  • Nakonec se C odstraní a fronta je prázdná, což znamená, že jsme hotovi.
  • Generovaný výstup je - A, B, D, G, E, F, C.

Aplikace-

BFS může být užitečné při zjištění, zda má graf připojené komponenty nebo ne. A také může být použit při detekci bipartitního grafu .

Graf je bipartitní, když jsou vrcholy grafu rozděleny do dvou disjunktních množin; žádné dva přilehlé vrcholy by neměly bydlet ve stejné sadě. 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

Metoda procházení hloubkového prvního vyhledávání (DFS) používá zásobník pro ukládání navštívených vrcholů. DFS je metoda založená na hranách a pracuje v rekurzivním módu, kde jsou vrcholy prozkoumány podél cesty (hrany). Průzkum uzlu je pozastaven, jakmile je nalezen další neprozkoumaný uzel a nejpřesněji prozkoumány nejhlubší uzly. DFS projde / navštíví každý vrchol přesně jednou a každá hrana je zkontrolována přesně dvakrát.

Příklad

Podobně jako u BFS lze použít stejný graf pro provádění operací DFS a příslušné kroky jsou:

  • Vzhledem k tomu, že A je výchozím vrcholem, který je prozkoumán a uložen v zásobníku.
  • B nástupce vrcholu A je uložen v zásobníku.
  • Vertex B má dva nástupce E a F, mezi nimi je abecedně E prozkoumán 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 připojené vrcholy a oba jsou již navštíveny, takže G je vyskakován ze zásobníku.
  • Stejně tak E odstraněn.
  • Vrchol B je nyní v horní části zásobníku, jeho další uzel (vertex) F je prozkoumán a uložen v zásobníku.
  • Vertex F má dva nástupce C a D, mezi nimi se nejprve C přesune a uloží do 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í je navštíven vertex D spojený s F a uložen v zásobníku.
  • Jelikož vrchol D nemá žádné nenavštívené uzly, je D odstraněn.
  • Podobně jsou také zobrazeny F, B a A.
  • Generovaný výstup je - A, B, E, G, F, C, D.

Aplikace-

Aplikace DFS zahrnují kontrolu dvou hranového grafu, silně propojeného grafu, acyklického grafu a topologického řádu .

Graf se nazývá dvě hrany připojené pouze tehdy, když zůstane připojen, i když je odstraněn jeden z jeho okrajů. Tato aplikace je velmi užitečná, v počítačových sítích, kde selhání jednoho spojení v síti neovlivní zbývající síť a bude stále připojeno.

Silně spojený graf je graf, ve kterém musí existovat cesta mezi uspořádaným párem vrcholů. DFS se používá v řízeném grafu pro vyhledávání cesty mezi každým uspořádaným párem vrcholů. DFS může snadno vyřešit problémy s připojením.

Klíčové rozdíly mezi BFS a DFS

  1. BFS je vertexový algoritmus, zatímco DFS je algoritmus založený na hranách.
  2. Datová struktura fronty se používá v BFS. Na druhé straně DFS používá zásobník nebo rekurzi.
  3. Paměťový prostor je efektivně využíván v DFS, zatímco využití prostoru v BFS není efektivní.
  4. BFS je optimální algoritmus, zatímco DFS není optimální.
  5. DFS konstruuje úzké a dlouhé stromy. Jako proti, BFS konstruuje široký a krátký strom.

Závěr

BFS a DFS, obě techniky prohledávání grafů mají podobnou dobu běhu, ale rozdílnou spotřebu prostoru, DFS bere lineární prostor, protože si musíme pamatovat jednu cestu s neprozkoumanými 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.

Top