Čo je to Algoritmus BFS (vyhľadávanie na šírku)?
Vyhľadávanie na šírku (BFS) je algoritmus, ktorý sa používa na grafovanie údajov alebo prehľadávanie stromu alebo prechádzanie štruktúr. Plná forma BFS je hľadanie na šírku.
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. Pamätajte, že BFS pristupuje k týmto uzlom jeden po druhom.
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.
V tomto výučbe algoritmu sa dozviete:
- Čo je to Algoritmus BFS (vyhľadávanie na šírku)?
- Čo je to Graph Traversals?
- Architektúra algoritmu BFS
- Prečo potrebujeme algoritmus BFS?
- Ako funguje BFS algoritmus?
- Príklad algoritmu BFS
- Pravidlá algoritmu BFS
- Aplikácie BFS algoritmu
Čo je to Graph Traversals?
Traverzovanie grafu je bežne používanou metodikou lokalizácie polohy vrcholu v grafe. Jedná sa o pokročilý vyhľadávací algoritmus, ktorý dokáže analyzovať graf s rýchlosťou a presnosťou spolu s vyznačením sekvencie navštívených vrcholov. Tento proces umožňuje rýchlo navštíviť každý uzol v grafe bez toho, aby ste boli uzamknutí v nekonečnej slučke.
Architektúra algoritmu BFS
- Na rôznych úrovniach údajov môžete označiť ľubovoľný uzol ako počiatočný alebo počiatočný uzol, aby ste mohli začať prechádzať. BFS navštívi uzol, označí ho ako navštívený a umiestni ho do poradia.
- Teraz BFS navštívi najbližšie a nenavštívené uzly a označí ich. Tieto hodnoty sa tiež pridajú do frontu. Fronta funguje na modeli FIFO.
- Podobným spôsobom sa analyzujú zostávajúce najbližšie a nenavštívené uzly v grafe, ktoré sa označia a pridajú do poradia. Tieto položky sa odstránia z frontu ako prijaté a ako výsledok sa vytlačia.
Prečo potrebujeme algoritmus BFS?
Existuje mnoho dôvodov, prečo použiť algoritmus BFS na použitie pri vyhľadávaní vašej množiny údajov. Niektoré z najdôležitejších aspektov, vďaka ktorým je tento algoritmus vašou prvou voľbou, sú:
- BFS je užitočný na analýzu uzlov v grafe a na zostrojenie najkratšej cesty prechádzania cez tieto uzly.
- BFS môže prechádzať grafom v najmenšom počte iterácií.
- Architektúra algoritmu BFS je jednoduchá a robustná.
- Výsledok algoritmu BFS má vysokú úroveň presnosti v porovnaní s inými algoritmami.
- IFS iterácie BFS sú bezproblémové a nie je možné, aby sa tento algoritmus dostal do problému nekonečnej slučky.
Ako funguje BFS algoritmus?
Prechod grafu vyžaduje, aby algoritmus navštívil, skontroloval a / alebo aktualizoval každý jeden nenavštívený uzol v stromovej štruktúre. Prechody grafov sú kategorizované podľa poradia, v akom navštevujú uzly na grafe.
Algoritmus BFS spustí operáciu od prvého alebo počiatočného uzla v grafe a dôkladne ju prekoná. Akonáhle úspešne prekoná počiatočný uzol, potom sa navštívi a označí ďalší neprechodený vrchol v grafe.
Dá sa teda povedať, že všetky uzly susediace s aktuálnym vrcholom sú navštívené a prekonané v prvej iterácii. Na implementáciu práce s algoritmom BFS sa používa jednoduchá metodika radov, ktorá sa skladá z nasledujúcich krokov:
Krok 1)
Každý vrchol alebo uzol v grafe je známy. Napríklad môžete uzol označiť ako V.
Krok 2)
Ak nie je prístup na vrchol V, pridajte vrchol V do frontu BFS
Krok 3)
Spustite vyhľadávanie BFS a po dokončení označte vrchol V ako navštívený.
Krok 4)
Fronta BFS stále nie je prázdna, a preto z nej odstráňte vrchol V grafu.
Krok 5)
Načítajte všetky zostávajúce vrcholy v grafe, ktoré susedia s vrcholom V
Krok 6)
Pre každý susedný vrchol povedzme V1, v prípade, že ešte nie je navštívený, pridajte V1 do frontu BFS
Krok 7)
BFS navštívi V1, označí ho ako navštívený a vymaže ho z poradia.
Príklad algoritmu 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.
Pravidlá algoritmu BFS
Tu sú dôležité pravidlá pre používanie algoritmu BFS:
- BFS používa dátovú štruktúru frontu (FIFO-prvý dovnútra).
- Ktorýkoľvek uzol v grafe označíte ako root a začnete z neho prechádzať údaje.
- BFS prekonáva všetky uzly v grafe a neustále ich vysúva ako dokončené.
- BFS navštívi susedný nenavštívený uzol, označí ho ako hotový a vloží ho do poradia.
- Odstráni predchádzajúci vrchol z frontu v prípade, že sa nenájde žiadny susedný vrchol.
- Algoritmus BFS iteruje, kým nie sú všetky vrcholy v grafe úspešne prekonané a označené ako dokončené.
- Neexistujú žiadne slučky spôsobené BFS počas prechodu dát z ktoréhokoľvek uzla.
Aplikácie BFS algoritmu
Pozrime sa na niektoré z reálnych aplikácií, kde implementácia algoritmu BFS môže byť vysoko efektívna.
- Nevážené grafy: Algoritmus BFS dokáže ľahko vytvoriť najkratšiu cestu a minimálny spanningový strom, aby ste s vysokou presnosťou navštívili všetky vrcholy grafu v čo najkratšom čase.
- Siete P2P: Je možné implementovať BFS na lokalizáciu všetkých najbližších alebo susedných uzlov v sieti typu peer to peer. Takto rýchlejšie nájdete požadované údaje.
- Webové prehľadávače : Vyhľadávacie stroje alebo webové prehľadávače môžu ľahko vytvárať viac úrovní indexov pomocou BFS. 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.
- Navigačné systémy: BFS môže pomôcť nájsť všetky susedné miesta z hlavného alebo zdrojového umiestnenia.
- Sieťové vysielanie: Vysielaný paket je vedený algoritmom BFS tak, aby našiel a dosiahol všetky uzly, pre ktoré má adresu.
Zhrnutie
- Prechod grafu je jedinečný proces, ktorý vyžaduje, aby algoritmus navštívil, skontroloval a / alebo aktualizoval každý jeden nenavštívený uzol v stromovej štruktúre. Algoritmus BFS funguje na podobnom princípe.
- Algoritmus je užitočný na analýzu uzlov v grafe a na zostavenie najkratšej cesty prechádzania cez tieto uzly.
- Algoritmus prechádza grafom v najmenšom počte iterácií a v čo najkratšom čase.
- BFS vyberie jeden uzol (počiatočný alebo zdrojový bod) v grafe a potom navštívi všetky uzly susediace s vybraným uzlom. BFS pristupuje k týmto uzlom jeden po druhom.
- Navštívené a označené údaje umiestni BFS do poradia. Fronta funguje na princípe „prvý do prvého“. Preto sa prvok umiestnený v grafe ako prvý najskôr odstráni a vo výsledku sa vytlačí.
- Algoritmus BFS sa nikdy nemôže zachytiť v nekonečnej slučke.
- Vďaka vysokej presnosti a robustnej implementácii sa BFS používa v mnohých riešeniach z reálneho života, ako sú siete P2P, webové prehľadávače a sieťové vysielanie.