Algoritmus prvního vyhledávání šířky (BFS) s PŘÍKLADEM

Co je to BFS Algorithm (Breadth-First Search)?

Breadth-first search (BFS) je algoritmus, který se používá ke grafu dat nebo prohledávání stromu nebo procházení struktur. Úplnou formou BFS je vyhledávání do šířky.

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. Pamatujte, že BFS přistupuje k těmto uzlům jeden po druhém.

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.

Co je to Graph traversals?

Procházení 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 označením sekvence navštívených vrcholů. Tento proces vám umožňuje rychle navštívit každý uzel v grafu, aniž byste byli uzavřeni v nekonečné smyčce.

Architektura algoritmu BFS

1. V různých úrovních dat můžete označit libovolný uzel jako počáteční nebo počáteční uzel pro zahájení procházení. BFS navštíví uzel a označí jej jako navštívený a zařadí jej do fronty.
2. Nyní BFS navštíví nejbližší a nenavštívené uzly a označí je. Tyto hodnoty jsou také přidány do fronty. Fronta funguje na FIFO model.
3. Podobným způsobem jsou analyzovány zbývající nejbližší a nenavštívené uzly v grafu označené 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 algoritmus BFS?

Existuje mnoho důvodů, proč použít algoritmus BFS k hledání vaší datové sady. Některé z nejdůležitějších aspektů, díky kterým je tento algoritmus vaší první volbou, jsou:

• BFS je užitečný pro analýzu uzlů v grafu a sestrojení nejkratší cesty k jejich procházení.
• BFS může procházet grafem v nejmenším počtu iterací.
• Architektura algoritmu BFS je jednoduchá a robustní.
• Výsledek algoritmu BFS má ve srovnání s jinými algoritmy vysokou úroveň přesnosti.
• Iterace BFS jsou bezproblémové a neexistuje žádná možnost, že by se tento algoritmus dostal do problému s nekonečnou smyčkou.

Jak funguje algoritmus BFS?

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. Průchody grafů jsou kategorizovány podle pořadí, ve kterém navštíví uzly v grafu.

Algoritmus BFS spustí operaci od prvního nebo počátečního uzlu v grafu a důkladně jej projde. Jakmile úspěšně projde počátečním uzlem, navštíví se a označí další nepřekročený vrchol v grafu.

Dá se tedy ří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 označit uzel jako V.

Krok 2)

V případě, že k vrcholu V není přístup, 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)

Získejte všechny zbývající vrcholy v grafu, které sousedí s vrcholem V

Krok 6)

Pro každý sousední vrchol řekněme V1, v případě, že ještě není navštíven, přidejte V1 do fronty BFS

Krok 7)

BFS navštíví V1 a označí ji jako navštívenou a odstraní ji z fronty.

Příklad algoritmu 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.

Pravidla algoritmu BFS

Zde jsou důležitá pravidla pro používání algoritmu BFS:

• Fronta (FIFO-First in First Out) datová struktura používá BFS.
• Libovolný uzel v grafu označíte jako kořenový a začnete z něj procházet data.
• BFS prochází všechny uzly v grafu a neustále je pouští jako dokončené.
• BFS navštíví sousední nenavštívený uzel, označí jej jako dokončený a vloží jej do fronty.
• Odebere předchozí vrchol z fronty v případě, že není nalezen žádný sousední vrchol.
• Algoritmus BFS iteruje, dokud nejsou všechny vrcholy v grafu úspěšně překročeny a označeny jako dokončené.
• Neexistují žádné smyčky způsobené BFS během procházení dat z jakéhokoli uzlu.

Aplikace algoritmu BFS

Podívejme se na některé z reálných aplikací, kde může být implementace algoritmu BFS vysoce efektivní.

• 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.
• Navigační systémy: BFS může pomoci najít všechna sousední umístění z hlavního nebo zdrojového umístění.
• 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.

Shrnutí

• Procházení grafu je jedinečný proces, který vyžaduje, aby algoritmus navštívil, zkontroloval a/nebo aktualizoval každý jednotlivý 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 sestrojení nejkratší cesty k jejich procházení.
• Algoritmus prochází grafem v co nejmenším počtu iterací a v nejkratším možném čase.
• BFS 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. BFS přistupuje k těmto uzlům jeden po druhém.
• Navštívená a označená data BFS zařadí do fronty. Fronta funguje na principu první dovnitř, první ven. Prvek umístěný v grafu jako první je tedy odstraněn jako první a vytištěn.
• Algoritmus BFS se nikdy nemůže dostat do nekonečné smyčky.
• Díky vysoké přesnosti a robustní implementaci se BFS používá v mnoha reálných řešeních, jako jsou P2P sítě, webové prohledávače a síťové vysílání.