Prohledávání do šířky

Prohledávání do šířky (anglicky Breadth-first search, zkráceně BFS) je grafový algoritmus, který postupně prochází všechny vrcholy v dané komponentě souvislosti. Algoritmus nejprve projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti.

Jak funguje

Prohledávání do šířky je algoritmus či metoda, která postupuje systematickým prohledáváním grafu přes všechny uzly. Nepoužívá při svém prohledávání žádnou heuristickou analýzu. Pouze prochází všechny uzly a pro každý projde jejich všechny následovníky. Přitom si poznamenává předchůdce jednotlivých uzlů a tím je poté vytvořen strom nejkratších cest k jednotlivým uzlům z kořene (uzlu v kterém jsme začínali).

Z hlediska algoritmu, veškeří následovníci uzlu získaní expandujícím uzlem jsou vkládani do FIFO fronty. FIFO fronta znamená, že první uzel, který do fronty vstoupil jí také první opustí. V typických implementacích jsou uzly, které nebyly ještě objeveny, označeny jako FRESH. Uzly které se dostávají do fronty, které jsou v této chvíli právě vyšetřovány na jejich následníky jsou označeny jako OPEN a naposled uzly, které z fronty byly už vybrány a už s nimi nebudeme pracovat, jsou označeny jako CLOSE. Close uzly již nikdy v tomto běhu algoritmu nebudou prozkoumávany, mají vyplněné všechny informace. To znamená vzdálenost od kořenového (počátečního) uzlu, stav uzlu (CLOSE) a předchůdce.

Příklad mapy Německa s propojeními mezi městy.

Strom vzniklý algoritmem prohledání do šířky, které startuje ve Frankfurtu.

Obecná implementace v pseudokódu

 1 void BFS (Graph G, Node s) {   
 2   for (Node u in U(G)-s)
 3     { stav[u] = FRESH; d[u] = nekonečno; p[u] = null; }
 4   stav[s] = OPEN; d[s] = 0; p[s] = null;
 5   Queue.Init(); Queue.Push(s);
 6   while (!Queue.Empty()) {
 7     u = Queue.Pop();
 8     for (v in Adj[u]) {
 9       if (stav[v] == FRESH) {
10         stav[v] = OPEN; d[v] = d[u]+1;
11         p[v] = u; Queue.Push(v); 
12       }
13     }
14     stav[u]=CLOSED;
15   }
16 }

Popis algoritmu

Na počátku algoritmu se provede inicializace. Poté se nastaví počáteční hodnoty pro jediný uzel, u kterého známe všechny informace a to pro počáteční uzel (viz stav při inicializaci). Nyní se rozběhne cyklus, který běží dokud je FIFO fronta neprázdná. Neprázdná fronta znamená, že máme stále uzly s kterými pracujeme, jelikož do této fronty jsou vkládány pouze uzly s kterými nyní pracujeme. Na počátku cyklu z fronty vyjmeme uzel. Pro všechny následníky tohoto uzlu budeme zjišťovat jestli mají stav FRESH. Stav FRESH znamená, že uzel nebyl ještě nalezen ani prozkoumán. Když bude tato podmínka týkající se stavu splněna, nastaví se informace pro tyto uzly. Stav OPEN, vzdálenost od počátku o jedna větší než uzel kterého je tento uzel následník. Vzdálenost je větší právě o jedna z důvodu, že je mezi těmito uzly pouze jedna hrana. Naposled se pro tyto následníky uzlu (u) nastaví předchůdce právě na hodnotu (u). Po nastavení všech těchto vlastností je uzel vložen do fronty. Když jsou prohledáni všichni následníci daného uzlu, tak se uzel uzavře, stav uzlu se bude rovnat CLOSE.

Použité datové struktury

1) FIFO fronta - fronta, do které jsou ukládány uzly s kterými právě pracujeme. To znamená, ve frontě jsou uzly,
   které představují jakoby "vlnu" provádění algoritmu.

2) Pole vzdáleností - V tomto poli jsou uloženy vzdálenosti (počty hran na nejkratší cestě mezi uzly) jednotlivých 
   uzlů od počátku.

3) Pole předchůdců - V tomto poli jsou uloženy předchůdci jednotlivých uzlů. Z tohoto pole se poté konstruuje strom 
   nejkratších cest.

4) Pole stavů - V tomto poli jsou uloženy stavy jednotlivých uzlů.

Stav při inicializaci

Všechny tyto datové struktury jsou na počátku algoritmu inicializované. Fifo fronta je inicializovaná jako prázdná fronta. V poli vzdáleností mají všechny prvky na počátku hodnotu nekonečno. Nekonečno je nastaveno proto, jelikož by cesta byla nekonečně daleká neboli, že neexistuje. Opačná hodnota nula je nastavena na začátku pouze uzlu počátečnímu, z kterého bude algoritmus začínat svůj běh. Nulová vzdálenost znamená, že se jedná o totožný uzel. Pole stavů je nastaveno na počátku na hodnoty FRESH pro všechny uzly mimo prvnímu který má stav OPEN. Pole předchůdců je nastaveno na null pro všechny uzly. Nakonec se do fronty vloží uzel s (startovací uzel). Velikosti jednotlivých polí jsou nastaveny na velikost shodnou s počtem uzlů v grafu.

Časová složitost

Asymptotická časová složitost algoritmu je ${\mathcal {O}}(|V|+|E|)$ , kde $V$ je množina vrcholů a $E$ je množina hran grafu.

Odvození

Inicializace algoritmu trvá ${\mathcal {O}}(|V|)$ . Každý z vrcholů uzavíráme nejvýše jednou, tj. vnější cyklus proběhne nejvýše $|V|$ -krát, přičemž v rámci každé iterace spotřebuje konstantní čas na svou režii a zpracování každého následníka. Počet následníků libovolného vrcholu $u\in V$ odpovídá (z definice) jeho stupni, tj. $\deg {u}$ . Časovou složitost lze tedy vyjádřit výrazem

{\mathcal {O}}\left(|V|+\sum _{u\in V}{\deg {u}}\right)

.

Uvedená suma bude (podle principu sudosti) rovna $2|E|$ . Tedy celkově dostáváme

{\mathcal {O}}\left(|V|+\sum _{u\in V}{\deg {u}}\right)={\mathcal {O}}\left(|V|+2|E|\right)={\mathcal {O}}\left(|V|+|E|\right).

Poznámka: Pro orientované grafy se bude odvození lišit, neboť v sumě budeme uvažovat výstupní stupeň vrcholu $u$ , tj. $\deg ^{-}{u}$ , přičemž bude platit

\sum _{u\in V}{\deg ^{-}{(u)}}=|E|

.

Prostorová složitost

Prostorová složitost je ${\mathcal {O}}(|V|+|E|)$ . Řečeno jinak, prostorová složitost je ${\mathcal {O}}(B^{M})$ , kde $B$ je nejvyšší stupeň větvení stromu a $M$ je nejvyšší délka cesty ve stromě. Tento velký nárok na prostor ve srovnání s nárokem prohledávání do hloubky je důvod, proč je prohledávání do šířky nepraktické pro rozsáhlejší problémy.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Prohledávání do šířky na Wikimedia Commons

Popis a implementace v ActionScriptu
Animace běhu algoritmu
Implementace v Pythonu
Jakub Černý: Základní grafové algoritmy (texty v pdf)