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í | BFS | DFS |
|---|---|---|
| Základní | Vertexový algoritmus | Algoritmus založený na hraně |
| Datová struktura pro uložení uzlů | Fronta | Zásobník |
| Spotřeba paměti | Neefektivní | Účinný |
| Struktura konstruovaného stromu | Široké a krátké | Úzké a dlouhé |
| Traversing móda | Nejdříve jsou prozkoumány nejstarší neviděné vrcholy. | Na začátku se zkoumají svislé hrany. |
| Optimality | Optimální pro nalezení nejkratší vzdálenosti, ne v nákladech. | Není optimální |
| aplikace | Zkoumá 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.
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 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
- BFS je vertexový algoritmus, zatímco DFS je algoritmus založený na hranách.
- Datová struktura fronty se používá v BFS. Na druhé straně 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 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.
