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á k vykreslení grafů dat, prohledávání stromu nebo procházení struktur. Úplná forma BFS je Breadth-first search.

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. Na různých úrovních dat můžete označit libovolný uzel jako počáteční nebo iniciální uzel pro zahájení procházení. BFS uzel navštíví, označí ho jako navštívený a zařadí ho do fronty.
2. BFS nyní navštíví nejbližší a nenavštívené uzly a označí je. Tyto hodnoty jsou také přidány do fronty. Fronta pracuje na FIFO model.
3. Podobným způsobem se analyzují, označí a přidají do fronty zbývající nejbližší a nenavštívené uzly v grafu. Tyto položky se z fronty odstraňují, jakmile jsou přijaty, a jako výsledek se vytisknou.

Proč potřebujeme algoritmus BFS?

Existuje mnoho důvodů, proč použít algoritmus BFS pro vyhledávání v datové sadě. Mezi nejdůležitější aspekty, které z tohoto algoritmu dělají vaši první volbu, patří:

• 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 projdeny v první iteraci. Pro implementaci fungování algoritmu BFS se používá jednoduchá metodologie front, 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 vrchol V není přístupný, 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)

Najděte všechny zbývající vrcholy grafu, které sousedí s vrcholem V.

Krok 6)

Pro každý sousední vrchol, řekněme V1, pokud ještě není navštíven, se do fronty BFS přidá V1.

Krok 7)

BFS navštíví V1, označí ji jako navštívenou a smaže ji z fronty.

Příklad algoritmu BFS

Krok 1)

Máte graf sedmi čísel v rozsahu od 0 do 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í uzly sousedící s nulou a nenavštívené uzly jsou navštíveny, označeny a vloženy 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.
• Označíte libovolný uzel v grafu jako kořen a od něj začnete procházet data.
• BFS prochází všemi uzly v grafu a udržuje dropping je jako dokončené.
• BFS navštíví sousední nenavštívený uzel, označí jej jako dokončený a vloží jej do fronty.
• Odstraní 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ě projety 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 dokáže snadno vytvořit nejkratší cestu a minimální kostru, aby navštívil všechny vrcholy grafu v co nejkratším čase s vysokou přesností.
• P2P sítě: BFS lze implementovat k lokalizaci všech nejbližších nebo sousedních uzlů v peer-to-peer síti. To umožní rychlejší nalezení požadovaných dat.
• 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.

Nejčastější dotazy