01 Algoritmus BFS
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Algoritmus BFS
- Například BFS, značíme jako $BFS(G, s)$ na grafu $G$ se startovním vrcholem $s$
- Funguje stejně pro neorientované grafy i orientované grafy
# Fáze
- Značíme $F$
- Fáze $F_0$ trvá od odebrání vrcholu $s$ z fronty $Q$, otevření a vložení všech jeho sousedů do $Q$ až do uzavření vrcholu $s$
- Fáze $F_i$ trvá od konce fáze $F_{i-1}$ až po uzavření všech vrcholů z $H_i$
- $h$ - číslo poslední fáze
# Hladina
- Značíme $H$
- $H_i$ je množina všech vrcholů otevřených a vložených do fronty $Q$ ve fázi $F_{i-1}$
Příklad hladin v grafu:
# Analýza složitosti BFS
(Souvisí s 02 Výpočetní model RAM)
# Časová složitost
Odůvodnění:
- Každý vrchol do BFS přidáme nejvýše jednou
- V každé iteraci je 1 vrchol odebrán z fronty, má tedy nejvýše $n$ iterací
- $\Rightarrow$ Asymptoticky $O(n+m)$ - lineární
- $n$ = počet vrcholů
- $m$ = počet hran
# Paměťová složitost
- Lepší je seznam sousedů oproti 2D matici
- Pole stav, pole sousedů, fronta
- $\Rightarrow$ Asymptoticky $O(n+n)$ - lineární