BFS vs DFS – rozdíl mezi nimi

Co je BFS?

BFS je algoritmus, který se používá ke grafu dat nebo prohledávání stromu nebo procházení struktur. Algoritmus efektivně navštíví a označí všechny klíčové uzly v grafu přesným způsobem po šířce.

Tento algoritmus vybere jeden uzel (počáteční nebo zdrojový bod) v grafu a poté navštíví všechny uzly sousedící s vybraným uzlem. Jakmile algoritmus navštíví a označí počáteční uzel, přesune se k nejbližším nenavštíveným uzlům a analyzuje je.

Po návštěvě jsou všechny uzly označeny. Tyto iterace pokračují, dokud nejsou všechny uzly grafu úspěšně navštíveny a označeny. Úplnou formou BFS je vyhledávání do šířky.

Co je DFS?

DFS je algoritmus pro hledání nebo procházení grafů nebo stromů ve směru do hloubky. Provádění algoritmu začíná v kořenovém uzlu a prozkoumává každou větev, než se vrátí zpět. Kdykoli se v jakékoli iteraci objeví slepá ulička, používá datovou strukturu zásobníku k zapamatování, získání následného vrcholu a zahájení vyhledávání. Úplná forma DFS je hloubkové vyhledávání.

Rozdíl mezi BFS a DFS binárním stromem

Zde jsou důležité rozdíly mezi BFS a DFS.

BFS	DFS
BFS najde nejkratší cestu k cíli.	DFS přejde na konec podstromu a poté se vrátí zpět.
Plná forma BFS je Breadth-First Search.	Plná forma DFS je Depth First Search.
Používá frontu ke sledování dalšího místa k návštěvě.	Používá zásobník ke sledování dalšího místa k návštěvě.
BFS prochází podle úrovně stromu.	DFS se pohybuje podle hloubky stromu.
Je implementován pomocí seznamu FIFO.	Je implementován pomocí seznamu LIFO.
Vyžaduje více paměti ve srovnání s DFS.	Vyžaduje méně paměti ve srovnání s BFS.
Tento algoritmus poskytuje řešení s nejmělčí cestou.	Tento algoritmus nezaručuje řešení nejmělčí cesty.
V BFS není potřeba zpětného sledování.	V DFS je potřeba backtracking.
Nikdy nemůžete být uvězněni v konečných smyčkách.	Můžete být uvězněni v nekonečných smyčkách.
Pokud nenajdete žádný cíl, možná budete muset rozšířit mnoho uzlů, než bude nalezeno řešení.	Pokud nenajdete žádný cíl, může dojít ke zpětnému sledování listového uzlu.

Příklad BFS

V následujícím příkladu BFS jsme použili graf se 6 vrcholy.

Příklad BFS

Krok 1)

Máte k dispozici graf sedmi čísel v rozmezí 0 – 6.

Krok 2)

0 nebo nula byla označena jako kořenový uzel.

Krok 3)

0 je navštíven, označen a vložen do datové struktury fronty.

Krok 4)

Zbývajících 0 sousedních a nenavštívených uzlů je navštíveno, označeno a vloženo do fronty.

Krok 5)

Iterace procházení se opakují, dokud nejsou navštíveny všechny uzly.

Příklad DFS

V následujícím příkladu DFS jsme použili neorientovaný graf s 5 vrcholy.

Krok 1)

Začali jsme od vrcholu 0. Algoritmus začíná jeho vložením do navštíveného seznamu a současně vložením všech jeho sousedních vrcholů do datová struktura nazývaný zásobník.

Krok 2)

Navštívíte prvek, který je v horní části zásobníku, například 1, a přejdete k jeho sousedním uzlům. Je to proto, že 0 již byla navštívena. Proto navštívíme vrchol 2.

Krok 3)

Vertex 2 má nenavštívený blízký vrchol ve 4. Proto jej přidáme do zásobníku a navštívíme jej.

Krok 4)

Nakonec navštívíme poslední vrchol 3, který nemá žádné nenavštívené sousední uzly. Dokončili jsme procházení grafu pomocí algoritmu DFS.

Aplikace BFS

Zde jsou aplikace BFS:

Nevážené grafy

Algoritmus BFS může snadno vytvořit nejkratší cestu a minimální kostru pro návštěvu všech vrcholů grafu v co nejkratším čase s vysokou přesností.

P2P sítě

BFS lze implementovat k vyhledání všech nejbližších nebo sousedních uzlů v síti peer to peer. Potřebná data tak najdete rychleji.

Prohledávače webu

Vyhledávače nebo webové prohledávače mohou snadno vytvořit více úrovní indexů pomocí BFS. Implementace BFS začíná od zdroje, kterým je webová stránka, a poté navštíví všechny odkazy z tohoto zdroje.

Síťové vysílání

Vysílaný paket je řízen algoritmem BFS, aby našel a dosáhl všech uzlů, pro které má adresu.

Aplikace DFS

Zde jsou důležité aplikace DFS:

Vážený graf

Ve váženém grafu generuje procházení grafu DFS strom nejkratší cesty a minimální kostru.

Detekce cyklu v grafu

Graf má cyklus, pokud jsme během DFS našli zadní hranu. Proto bychom měli spustit DFS pro graf a ověřit zadní hrany.

Hledání cesty

Můžeme se specializovat na algoritmus DFS pro hledání cesty mezi dvěma vrcholy.

Topologické třídění

Primárně se používá pro plánování úloh z daných závislostí mezi skupinou úloh. V informatice se používá při plánování instrukcí, serializaci dat, logické syntéze, určování pořadí kompilačních úloh.

Hledání silně propojených součástí grafu

Používá se v grafu DFS, když existuje cesta z každého a každého vrcholu v grafu k dalším zbývajícím vrcholům.

Řešení hádanek pouze s jedním řešením

Algoritmus DFS lze snadno přizpůsobit pro vyhledávání všech řešení bludiště zahrnutím uzlů na existující cestě do navštívené sady.