Co je BFS?
BFS je algoritmus, který se používá ke grafování 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řesnou šířkou.
Tento algoritmus vybere v grafu jeden uzel (počáteční nebo zdrojový bod) 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, posune se k nejbližším nenavštíveným uzlům a analyzuje je.
Po návštěvě jsou označeny všechny uzly. Tyto iterace pokračují, dokud nebudou úspěšně navštíveny a označeny všechny uzly grafu. Plnou formou BFS je vyhledávání na šířku.
V tomto BSF vs. Výukový program DFS Binární strom, naučíte se:
- Co je BFS?
- Co je DFS?
- Příklad BFS
- Příklad DFS
- Rozdíl mezi binárním stromem BFS a DFS
- Aplikace BFS
- Aplikace DFS
Co je DFS?
DFS je algoritmus pro hledání nebo procházení grafů nebo stromů ve směru hloubky. Provedení algoritmu začíná v kořenovém uzlu a zkoumá každou větev před zpětným sledováním. Používá strukturu dat zásobníku k zapamatování, k získání následného vrcholu ak zahájení vyhledávání, kdykoli se v jakékoli iteraci objeví slepá ulička. Plnou formou DFS je vyhledávání do hloubky.
Příklad BFS
V následujícím příkladu DFS jsme použili graf mající 6 vrcholů.
Příklad BFS
Krok 1)
K dispozici je graf sedmi čísel od 0 do 6.
Krok 2)
0 nebo nula byla označena jako kořenový uzel.
Krok 3)
0 je navštívena, označena a vložena do datové struktury fronty.
Krok 4)
Zbývající 0 sousedních a nenavštívených uzlů je navštíveno, označeno a vloženo do fronty.
Krok 5)
Traverské iterace se opakují, dokud nenavštívíte 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á vložením do navštíveného seznamu a současným vložením všech jeho sousedních vrcholů do datové struktury zvané stack.
Krok 2)
Navštívíte prvek, který je v horní části zásobníku, například 1, a přejdete do jeho sousedních uzlů. Je to proto, že 0 již byla navštívena. Proto navštěvujeme vrchol 2.
Krok 3)
Vertex 2 má nenavštívený blízký vrchol v 4. Proto přidáme, že v zásobníku a navštívit jej.
Krok 4)
Nakonec navštívíme poslední vrchol 3, který nemá žádné nenavštívené sousední uzly. Prochod grafu jsme dokončili pomocí algoritmu DFS.
Rozdíl mezi binárním stromem 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. |
| Plnou formou BFS je Breadth-First Search. | Plnou formou DFS je Depth First Search. |
| Používá frontu ke sledování dalšího místa k návštěvě. | Využívá hromádku ke sledování dalšího místa k návštěvě. |
| BFS prochází podle úrovně stromu. | DFS prochází podle hloubky stromu. |
| Implementuje se pomocí seznamu FIFO. | Implementuje se 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í pro nejmělčí cestu. | Tento algoritmus nezaručuje řešení mělké cesty. |
| V BFS není potřeba zpětného sledování. | V DFS je potřeba zpětného sledování. |
| Nikdy nemůžete být uvězněni v omezený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 před nalezením řešení rozšířit mnoho uzlů. | Pokud nenajdete žádný cíl, může dojít k zpětnému sledování listového uzlu. |
Aplikace BFS
Zde jsou aplikace BFS:
Nevážené grafy:
Algoritmus BFS může snadno vytvořit nejkratší cestu a minimální kostru, aby mohl s vysokou přesností navštívit všechny vrcholy grafu v co nejkratším čase.
Sítě P2P:
Může být implementován BFS k vyhledání všech nejbližších nebo sousedních uzlů v síti typu peer to peer. Tím vyhledáte požadovaná data rychleji.
Prohledávače webu:
Vyhledávací stroje nebo webové prohledávače mohou snadno vytvářet 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 veden algoritmem BFS k nalezení a dosažení 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 přechod DFS grafu nejkratší strom 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 pro graf spustit DFS 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í:
To se používá především pro plánování úloh z uvedených závislostí mezi skupiny pracovních míst. V počítačové vědě se používá při plánování instrukcí, serializaci dat, logické syntéze, určování pořadí úkolů kompilace.
Hledání silně propojených komponent grafu:
Používá se v grafu DFS, když existuje cesta z 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 prohledávání všech řešení bludiště zahrnutím uzlů na existující cestě v navštívené sadě.
KLÍČOVÉ ROZDÍLY:
- BFS najde nejkratší cestu k cíli, zatímco DFS přejde na konec podstromu a poté se vrátí zpět.
- Plná forma BFS je Breadth-First Search, zatímco plná forma DFS je Depth First Search.
- BFS používá frontu ke sledování dalšího místa k návštěvě. vzhledem k tomu, že DFS používá hromádku ke sledování dalšího místa k návštěvě.
- BFS prochází podle úrovně stromu, zatímco DFS prochází podle hloubky stromu.
- BFS je implementován pomocí seznamu FIFO, na druhé straně DFS je implementován pomocí seznamu LIFO.
- V BFS nikdy nemůžete být uvězněni do konečných smyček, zatímco v DFS můžete být uvězněni do nekonečných smyček.