Čo je to BFS?
BFS je algoritmus, ktorý sa používa na vytváranie grafov údajov alebo prehľadávanie stromov alebo prechádzanie štruktúr. Algoritmus efektívne navštevuje a označuje všetky kľúčové uzly v grafe presným spôsobom po šírke.
Tento algoritmus vyberie v grafe jeden uzol (počiatočný alebo zdrojový bod) a potom navštívi všetky uzly susediace s vybraným uzlom. Akonáhle algoritmus navštívi a označí začiatočný uzol, potom sa presunie k najbližším nenavštíveným uzlom a analyzuje ich.
Po návšteve sú všetky uzly označené. Tieto iterácie pokračujú, kým nebudú úspešne navštívené a označené všetky uzly grafu. Plná forma BFS je hľadanie na šírku.
V tomto BSF vs. Výukový program DFS Binárny strom, naučíte sa:
- Čo je to BFS?
- Čo je to DFS?
- Príklad BFS
- Príklad DFS
- Rozdiel medzi binárnym stromom BFS a DFS
- Aplikácie BFS
- Aplikácie DFS
Čo je to DFS?
DFS je algoritmus na hľadanie alebo prechádzanie grafov alebo stromov v smere hĺbky. Vykonanie algoritmu začína v koreňovom uzle a pred spätným sledovaním skúma každú vetvu. Používa dátovú štruktúru zásobníka na zapamätanie, získanie následného vrcholu a začatie vyhľadávania, kedykoľvek sa v akejkoľvek iterácii objaví slepá ulička. Plnou formou DFS je vyhľadávanie podľa hĺbky.
Príklad BFS
V nasledujúcom príklade DFS sme použili graf so 6 vrcholmi.
Príklad BFS
Krok 1)
Máte graf siedmich čísel v rozmedzí od 0 do 6.
Krok 2)
0 alebo nula bola označená ako koreňový uzol.
Krok 3)
0 je navštívená, označená a vložená do dátovej štruktúry frontu.
Krok 4)
Zvyšných 0 susedných a nenavštívených uzlov sa navštívi, označí a vloží do frontu.
Krok 5)
Traverské iterácie sa opakujú, kým nie sú navštívené všetky uzly.
Príklad DFS
V nasledujúcom príklade DFS sme použili neorientovaný graf s 5 vrcholmi.
Krok 1)
Začali sme od vrcholu 0. Algoritmus začína jeho vložením do navštíveného zoznamu a súčasným vložením všetkých jeho susedných vrcholov do dátovej štruktúry zvanej stack.
Krok 2)
Navštívite prvok, ktorý je v hornej časti stohu, napríklad 1, a choďte do jeho susedných uzlov. Je to preto, že 0 už bola navštívená. Preto navštevujeme vrchol 2.
Krok 3)
Vertex 2 má nenavštívený blízky vrchol v 4. Preto ho pridáme do zásobníka a navštívime ho.
Krok 4)
Nakoniec navštívime posledný vrchol 3, ktorý nemá žiadne nenavštívené susedné uzly. Prechod grafu sme dokončili pomocou algoritmu DFS.
Rozdiel medzi binárnym stromom BFS a DFS
| BFS | DFS |
| BFS nájde najkratšiu cestu k cieľu. | DFS ide do dolnej časti podstromu a potom ustúpi. |
| Plnou formou BFS je vyhľadávanie na šírku. | Plnou formou DFS je Depth First Search. |
| Pomocou frontu sleduje ďalšie navštívené miesto. | Používa zásobník na sledovanie ďalšieho navštíveného miesta. |
| BFS prechádza podľa úrovne stromu. | DFS prechádza podľa hĺbky stromu. |
| Implementuje sa pomocou zoznamu FIFO. | Implementuje sa pomocou zoznamu LIFO. |
| Vyžaduje viac pamäte v porovnaní s DFS. | Vyžaduje menej pamäte v porovnaní s BFS. |
| Tento algoritmus poskytuje riešenie pre plytkú cestu. | Tento algoritmus nezaručuje riešenie plytkej cesty. |
| V BFS nie je potrebné spätné sledovanie. | V DFS je potreba spätného sledovania. |
| Nikdy nemôžete byť uväznení v konečných slučkách. | Môžete byť uväznení v nekonečných slučkách. |
| Ak nenájdete žiadny cieľ, možno budete musieť pred nájdením riešenia rozšíriť veľa uzlov. | Ak nenájdete žiadny cieľ, môže dôjsť k spätnému sledovaniu listového uzla. |
Aplikácie BFS
Tu sú aplikácie BFS:
Nevážené grafy:
Algoritmus BFS dokáže ľahko vytvoriť najkratšiu cestu a minimálny spanningový strom, aby s vysokou presnosťou navštívil všetky vrcholy grafu v čo najkratšom čase.
Siete P2P:
Môže byť implementovaný BFS na lokalizáciu všetkých najbližších alebo susedných uzlov v sieti peer to peer. Takto rýchlejšie nájdete požadované údaje.
Webové prehľadávače:
Vyhľadávacie nástroje alebo webové prehľadávače môžu pomocou BFS ľahko zostaviť viac úrovní indexov. Implementácia BFS sa začína od zdroja, ktorým je webová stránka, a potom navštívi všetky odkazy z tohto zdroja.
Sieťové vysielanie:
Vysielaný paket je vedený algoritmom BFS tak, aby našiel a dosiahol všetky uzly, pre ktoré má adresu.
Aplikácie DFS
Tu sú dôležité aplikácie DFS:
Vážený graf:
Vo váženom grafe generuje priečny graf DFS najkratšiu cestu a minimálnu dĺžku.
Zistenie cyklu v grafe:
Graf má cyklus, ak sme počas DFS našli zadnú hranu. Preto by sme mali pre graf spustiť DFS a overiť zadné hrany.
Hľadanie cesty:
Môžeme sa špecializovať na algoritmus DFS na hľadanie cesty medzi dvoma vrcholmi.
Topologické triedenie:
To sa používa predovšetkým pre plánovanie úloh z uvedených závislostí medzi skupiny pracovných miest. V informatike sa používa pri plánovaní inštrukcií, serializácii dát, logickej syntéze, určovaní poradia úloh kompilácie.
Vyhľadávanie silne prepojených komponentov grafu:
Používa sa v grafe DFS, keď existuje cesta z každého vrcholu v grafe k ďalším zostávajúcim vrcholom.
Riešenie hádaniek iba s jedným riešením:
Algoritmus DFS možno ľahko prispôsobiť tak, aby prehľadával všetky riešenia bludiska, a to zahrnutím uzlov na existujúcej ceste do navštívenej množiny.
KĽÚČOVÉ ROZDIELY:
- BFS nájde najkratšiu cestu k cieľu, zatiaľ čo DFS ide do dolnej časti podstromu a potom ustúpi.
- Plná forma BFS je Vyhľadávanie na šírku, zatiaľ čo úplná forma DFS je Vyhľadávanie na hĺbku.
- Spoločnosť BFS používa front na sledovanie ďalšieho navštíveného miesta. zatiaľ čo DFS používa zásobník na sledovanie ďalšieho navštíveného umiestnenia.
- BFS prechádza podľa úrovne stromu, zatiaľ čo DFS prechádza podľa hĺbky stromu.
- BFS sa implementuje pomocou zoznamu FIFO, na druhej strane DFS sa implementuje pomocou zoznamu LIFO.
- V BFS nikdy nemôžete byť uväznení do konečných slučiek, zatiaľ čo v DFS môžete byť uväznení do nekonečných slučiek.