Co je to BFS Algorithm (Breadth-First Search)?
Šířka první vyhledávání (BFS) je algoritmus, který se používá ke grafování dat nebo prohledávání stromu nebo procházení struktur. Plnou formou BFS je vyhledávání na šířku.
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. Nezapomeňte, že BFS přistupuje k těmto uzlům jeden po druhém.
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.
V tomto výukovém programu Algoritmus se naučíte:
- Co je to BFS Algorithm (Breadth-First Search)?
- Co je to Graph Traversals?
- Architektura algoritmu BFS
- Proč potřebujeme BFS Algorithm?
- Jak funguje BFS Algorithm?
- Příklad BFS algoritmu
- Pravidla algoritmu BFS
- Aplikace algoritmu BFS
Co je to Graph Traversals?
Traverz grafu je běžně používaná metodika pro lokalizaci polohy vrcholu v grafu. Jedná se o pokročilý vyhledávací algoritmus, který dokáže analyzovat graf s rychlostí a přesností spolu s vyznačením sekvence navštívených vrcholů. Tento proces umožňuje rychle navštívit každý uzel v grafu, aniž byste byli uzamčeni v nekonečné smyčce.
Architektura algoritmu BFS
- Na různých úrovních dat můžete označit libovolný uzel jako počáteční nebo počáteční uzel, který začne procházet. BFS navštíví uzel a označí jej jako navštívený a umístí jej do fronty.
- Nyní BFS navštíví nejbližší a nenavštívené uzly a označí je. Tyto hodnoty se také přidají do fronty. Fronta funguje na modelu FIFO.
- Podobným způsobem jsou analyzovány zbývající nejbližší a nenavštívené uzly v grafu, označeny a přidány do fronty. Tyto položky jsou odstraněny z fronty jako přijaté a vytištěny jako výsledek.
Proč potřebujeme BFS Algorithm?
Existuje mnoho důvodů, proč použít Algoritmus BFS, který lze použít při hledání vaší datové sady. Některé z nejdůležitějších aspektů, díky nimž je tento algoritmus vaší první volbou, jsou:
- BFS je užitečné pro analýzu uzlů v grafu a konstrukci nejkratší cesty procházení těmito uzly.
- BFS může procházet grafem v nejmenším počtu iterací.
- Architektura algoritmu BFS je jednoduchá a robustní.
- Výsledek algoritmu BFS má vysokou úroveň přesnosti ve srovnání s jinými algoritmy.
- IFS iterace BFS jsou bezproblémové a není možné, aby se tento algoritmus dostal do problému nekonečné smyčky.
Jak funguje BFS Algorithm?
Procházení grafu vyžaduje, aby algoritmus navštívil, zkontroloval a / nebo aktualizoval každý jednotlivý nenavštívený uzel ve stromové struktuře. Procházení grafů je kategorizováno podle pořadí, ve kterém navštíví uzly v grafu.
Algoritmus BFS spustí operaci z prvního nebo počátečního uzlu v grafu a důkladně ji projde. Jakmile úspěšně projde počátečním uzlem, je navštíven a označen další neprocházející vrchol v grafu.
Proto můžete říci, že všechny uzly sousedící s aktuálním vrcholem jsou navštíveny a procházeny v první iteraci. K implementaci fungování algoritmu BFS se používá jednoduchá metodika fronty, která se skládá z následujících kroků:
Krok 1)
Každý vrchol nebo uzel v grafu je známý. Například můžete uzel označit jako V.
Krok 2)
V případě, že není přístup k vrcholu V, přidejte vrchol V do fronty BFS
Krok 3)
Spusťte vyhledávání BFS a po dokončení označte vrchol V jako navštívený.
Krok 4)
Fronta BFS stále není prázdná, proto odstraňte vrchol V grafu z fronty.
Krok 5)
Načíst všechny zbývající vrcholy v grafu, které sousedí s vrcholem V
Krok 6)
Pro každý sousední vrchol řekněme V1, pokud ještě není navštíven, přidejte V1 do fronty BFS
Krok 7)
BFS navštíví V1 a označí jej jako navštívený a vymaže jej z fronty.
Příklad BFS algoritmu
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.
Pravidla algoritmu BFS
Tady jsou důležitá pravidla pro používání algoritmu BFS:
- BFS používá datovou strukturu fronty (FIFO-First in First Out).
- Označíte libovolný uzel v grafu jako root a začnete z něj procházet data.
- BFS prochází všechny uzly v grafu a stále je vypouští jako dokončené.
- BFS navštíví sousední nenavštívený uzel, označí jej jako vyřízený a vloží jej do fronty.
- Odebere předchozí vrchol z fronty pro případ, že by nebyl nalezen žádný sousední vrchol.
- Algoritmus BFS iteruje, dokud nejsou všechny vrcholy v grafu úspěšně překonány a označeny jako dokončené.
- Neexistují žádné smyčky způsobené BFS během procházení dat z libovolného uzlu.
Aplikace algoritmu BFS
Pojďme se podívat na některé z reálných aplikací, kde implementace algoritmu BFS může být vysoce efektivní.
- 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: BFS lze implementovat 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.
- Webové prohledávače : 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.
- Navigační systémy: BFS může pomoci najít všechna sousední místa z hlavního nebo zdrojového umístění.
- Síťové vysílání: Vysílaný paket je veden algoritmem BFS k nalezení a dosažení všech uzlů, pro které má adresu.
souhrn
- Traverz grafu je jedinečný proces, který vyžaduje, aby algoritmus navštívil, zkontroloval a / nebo aktualizoval každý jeden nenavštívený uzel ve stromové struktuře. Algoritmus BFS funguje na podobném principu.
- Algoritmus je užitečný pro analýzu uzlů v grafu a konstrukci nejkratší cesty jejich procházení.
- Algoritmus prochází grafem v nejmenším počtu iterací a v co nejkratším čase.
- BFS 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. BFS přistupuje k těmto uzlům jeden po druhém.
- Navštívená a označená data jsou umístěna do fronty BFS. Fronta funguje od prvního do prvního. Proto je prvek umístěný v grafu jako první odstraněn jako první a vytištěn jako výsledek.
- Algoritmus BFS se nikdy nemůže zachytit v nekonečné smyčce.
- Díky vysoké přesnosti a robustní implementaci se BFS používá v mnoha reálných řešeních, jako jsou sítě P2P, webové prohledávače a síťové vysílání.