5.1 BFS

1 Úvod 2 Grafy 3 Stromy 4 Kostry 5 Základní grafové algoritmy 5.1 BFS 5.2 DFS 5.3 TopSort 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 11 Dynamické programování Index Literatura

Definice 5.1 (Prohledávání do šířky / Breadth-first search)

Buď neorientovaný graf $G = (V,E)$ a startovní vrchol $s \in V$ vstupem BFS, pak výstupem bude

Pole vzdáleností $D$ takové, že
\begin{equation*} D[v] = \begin{cases} k & k \text{ je délka nejkratší } s\text{-}v\text{-cesty v } G \\ \text{undef.} & \text{neexistuje žádná } s\text{-}v\text{-cesta v } G \end{cases} \end{equation*}
Pole předchůdcu $P$ takové, že
\begin{equation*} P[v] = \begin{cases} w & w \text{ je před } v \text{ na nějaké nejkratší } s\text{-}v\text{-cestě v } G \\ \text{undef.} & \text{neexistuje žádná } s\text{-}v\text{-cesta v } G \end{cases} \end{equation*}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {BFS}{graf $G$, vrchol $s$}
    \FOR { $v$ in $V(G)$ }
        \STATE stav[$v$] := nenalezený
        \STATE D[$v$] := P[$v$] := undef
    \ENDFOR
    \STATE $Q$ := fronta obsahující jediný vrchol $s$
    \STATE $stav[$s$] := $ otevřený
    \STATE $D[$s$] := 0, P[$s$] := ⊥$
    \WHILE { fronta $Q$ je neprázdná }
        \STATE Odeber z $Q$ první vrchol, nechť to je $v$
        \FOR { soused $w$ vrcholu $v$ }
            \IF { stav[$w$] = nenalezený }
                \STATE stav[$w$] := otevřený
                \STATE D[$w$] := D[$v$] + 1
                \STATE P[$w$] := $v$
                \STATE Přidej $w$ na konec fronty $Q$
            \ENDIF
        \ENDFOR
        \STATE stav[$v$] := uzavřený
    \ENDWHILE
    \RETURN $(D, P)$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 5.1: Algoritmus BFS (graf G, vrchol s)

Věta 5.1 (O konečnosti algoritmu `BFS`)

Algoritmus BFS $(G, s)$ se vždy zastaví.

Každý vrchol je přidán do fronty $Q$ nejvýše jednou, neboť je předtím otevřen a nemůže už tedy vícekrát splnit podmínku na řádku (10), že je nenalezený.
V každé iteraci cyklu (7)–(15) je jeden vrchol odebrán z fronty.
% Algoritmus se tedy zastaví nejvýše po $|V(G)|$ iteracích cyklu (7)–(15).

$\square$

Definice 5.2 (`BFS` fáze $F_i$ a `BFS` hladiny $H_i$)

Hladina $H_0 = \{s\}$.
Fáze $F_0$ trvá od odebrání $s$ z $Q$, otevření a vložení všech jeho sousedů do $Q$ až do uzavření $s$.
Hladina $H_i$ je množina všech vrcholů otevřených a vložených do $Q$ ve fázi $F_{i−1}$.
Fáze $F_i$ trvá od konce fáze $F_{i−1}$ až po uzavření všech vrcholů z $H_i$ (zahrnuje tedy vybrání všech vrcholů z $H_i$ z $Q$, otevření jejich dosud nenalezených sousedů a vložení těchto sousedů do $Q$).
Nechť $h$ je číslo poslední fáze BFS ($G, s$) (po ní se BFS ($G, s$) zastaví).

Věta 5.2 (O správnosti algoritmu `BFS`)

Vlastost 1: Po skončení BFS ($G, s$) jsou uzavřené právě ty vrcholy, do kterých vede cesta ze startu $s$ a ostatní vrcholy zůstanou nenalezené.

Vlastost 2: Pro všechny uzavřené vrcholy v platí $D[v] = d(s, v) =$ délka nejkratší cesty ze startu $s$ do vrcholu $v$.

Vlastost 3: Pro všechny uzavřené vrcholy $v$ platí $[v] = w$, kde w je předchůdce $v$ na nějaké nejkratší cestě ze startu $s$ do vrcholu $v$.

Prvním otevřeným a následně uzavřeným vrcholem je start $s$.
BFS otvírá na řádku (11) všechny nové sousedy dříve otevřených vrcholů.
$(⊇)$ Vrchol tedy bude otevřen (a později pak uzavřen) pouze tehdy, když do něho ze startu $s$ vede posloupnost sousedních hran.
$(⊆)$ Naopak, existuje-li do vrcholu nějaká posloupnost sousedních hran z $s$, bude v průběhu algoritmu někdy otevřen.

Hladiny $H_i, i = 0, . . . , h$, tvoří rozklad množiny uzavřených vrcholů.

$\square$

Triviálně platí ve fázi $F_0$. Uvažujme fázi $F_i, i > 0$.
Pokud $v ∈ H_i$, pak $D[v] = i$ a tedy z $s$ do $v$ musí existovat cesta o $i$ hranách. Proto je vzdálenost $d(s, v) ≤ i$.
Ukážeme nyní, že nemůže existovat $s$ - $v$-cesta kratší než $i$. Pro spor, nechť existuje cesta $P$ z $s$ do $v$ délky $j$, kde $j < i$.
Protože $j < i$, musí dle holubníkového principu na $P$ existovat dva sousední vrcholy $w$ a $w′$ a dvě nesousední hladiny $H_k$ a $H_ℓ$ (tedy $|k − ℓ| > 1$) tak, že $w ∈ H_k$ a $w′ ∈ H_ℓ$.
To však není možné, neboť dva sousední vrcholy na P nutně musí ležet ve dvou sousedních hladinách. Spor.
Proto $d(s, v) = i = D[v]$.

$\square$

TBD

$\square$

5.1 BFS

Definice 5.1 (Prohledávání do šířky / Breadth-first search)

Věta 5.1 (O konečnosti algoritmu BFS)

Definice 5.2 (BFS fáze $F_i$ a BFS hladiny $H_i$)

Věta 5.2 (O správnosti algoritmu BFS)

Věta 5.1 (O konečnosti algoritmu `BFS`)

Definice 5.2 (`BFS` fáze $F_i$ a `BFS` hladiny $H_i$)

Věta 5.2 (O správnosti algoritmu `BFS`)