1.2 BFS

Algoritmus 1.1 (BFS)

Algoritmus BFS

Breadth-first search (prohledávání grafu do šířky)

Vstup

Neorientovaný graf \(G = (V, E)\) a vrchol \(s \in V\)

Výstup

Pole vzdáleností \(D\) takové, že:

\[ D [v] = \begin{cases} k & k \text{ je délka nejkratší s-v-cesty v } G, \\ \text{undef.} & \text{neexistuje žádná s-v-cesta v } G \end{cases} \]

Pole předchůdců \(P\) takové, že:

\[ P [v] = \begin{cases} w & w \text{ je před } v \text{ na nějaké nejkratší s-v-cestě v } G, \\ \text{undef.} & \text{neexistuje žádná s-v-cesta v } G \end{cases} \]

Algoritmus

Algoritmus BFS(graf \(G\), vrchol \(s\))

Pro každý vrchol v ∈ V (G):
    stav[v] := nenalezený
    D[v] := P[v] := undef
Q := fronta obsahující jediný vrchol s
stav[s] := otevřený
D[s] := 0, P[s] := ⊥
Dokud je fronta Q neprázdná:
    Odeber z Q první vrchol, nechť to je v
    Pro všechny sousedy w vrcholu v:
        Pokud stav[w] = nenalezený:
            stav[w] := otevřený
            D[w] := D[v] + 1
            P[w] := v
            Přidej w na konec fronty Q
    stav[v] := uzavřený
Vrať (D, P)

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

Věta o konečnosti BFS

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

Důkaz věty 1.1

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)\)

Pokud víme, že se algoritmus BFS(G, s) vždy zastaví, můžeme (a musíme) ukázat, že vždy vydá správný (očekávaný) výsledek. To znamená dokázat jeho 3 vlastnosti.

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

Věta o správnosti BFS

Vlastnost 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é.
Vlastnost 2: Pro všechny uzavřené vrcholy \(v\) platí \(D[v] = d(s, v) =\) délka nejkratší cesty ze startu \(s\) do vrcholu \(v\).
Vlastnost 3: Pro všechny uzavřené vrcholy \(v\) platí \(P [v] = w\), kde \(w\) je předchůdce \(v\) na nějaké nejkratší cestě ze startu \(s\) do vrcholu \(v\).

Před dokončením důkazu správnosti definujme BFS fáze a hladiny.

Definice 1.4 (BFS fáze \(F_{i}\) a BFS hladiny \(H_{i}\))

Fáze a Hladiny BFS

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í).

Důkaz Vlastnosti 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é.

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.

Neformální definice holubníkového principu (věta z BI-DML)

Jestliže n holubů vletí do k hnízd, přičemž k < n, pak v některém hnízdě musí být alespoň dva holubi.

Důkaz Vlastnosti 2

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

Triviálně platí ve fázi \(F_{0}\). Uvažujme fázi \(F_{i}\), \(i > 0\).
Pokud \(v \in 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_{l}\) (tedy \(|k − ℓ| > 1\)) tak, že \(w \in H_{k}\) a \(w′ \in H_{l}\).
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]\)