\input ../lecnotes.tex

\prednaska{3}{Prohledávání grafù}{}

\h{Prohledání do~¹íøky {\I Breadth-First Search -- BFS} }

Jde o grafový algoritmus, který postupnì prochází v¹echny vrcholy v~dané komponentì souvislosti.
Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd\dots
Díky tomuto zpùsobu procházení se nìkdy té¾ nazývá \uv{\I algoritmus vlny}, nebo» se z~poèáteèního vrcholu ¹íøí pomyslná vlna, která v~ka¾dém kroku nalezne v¹echny uzly, které mají od~poèáteèního vrcholu stejnou vzdálenost. Algoritmus se tedy skvìle hodí napøíklad pro hledání nejkrat¹í cesty mezi dvìma vrcholy v~grafu.

Zatím pøedpokládejme, ¾e graf, se kterým pracujeme, je orientovaný.
Orientovanou hranu $(u,v)$ z~$u$ do~$v$ budeme obvykle zkracovat jako $uv$.
Pro neorientované grafy bude v¹e obdobné.

\figure{praseci-graf.eps}{Praseèí graf a prùchod vlny skrz nìj}{55mm}

\s{Popis algoritmu:}
Na zaèátku vlo¾íme do~fronty $Q$ poèáteèní vrchol $v_0$. Dále si v~poli~$Z$
budeme pro ka¾dý vrchol pamatovat znaèku, zda jsme ho ji¾ nav¹tívili ($Z[v]=1$), èi
nikoli ($Z[v]=0$). Na poèátku jsou v¹echny znaèky nulové, jen vrchol~$v_0$, který
je oznaèen a vlo¾en do fronty.

V~ka¾dém dal¹ím kroku pak zkoumáme frontu $Q$: pokud není prázdná, vezmeme
z~ní první vrchol~$u$ a podíváme se na~v¹echny vrcholy~$v$, do nich¾ z~$u$
vede hrana. Pokud sousedi je¹tì nejsou oznaèení, tak je oznaèíme a pøidáme je do~fronty
k~následnému zpracování. Toto opakujeme, dokud není fronta prázdná.

\s{Algoritmus:}

\algo
\:$Q \leftarrow \{v_0\}$.
\:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
\:Dokud $Q \not= \emptyset $ opakujeme:
\::Vyzvedneme vrchol $u$ z~$Q$.
\::$\forall v: uv\in E$:
\:::Je-li $Z[v]=0 \Rightarrow Z[v] \leftarrow 1$, pøidáme $v$ do~$Q$.
\endalgo

\s{Pozorování:} {\I BFS} se zastaví.

\proof Zpracováváme jen vrcholy, které byly ve~frontì. Ka¾dý vrchol se dostane do~fronty maximálnì jednou. (Ka¾dý je oznaèen max. jednou, znaèky neodstraòujeme.)

\s{Lemma:} BFS($v_0$) oznaèí $v$ právì tehdy, kdy¾ existuje cesta z~$v_0$ do~$v$.

\proof 
\uv{$\Longrightarrow$}: 
Platí jako invariant po celou dobu bìhu algoritmu. To doká¾eme indukcí dle doby
bìhu algoritmu:

První krok indukce je triviální, nebo» cesta z~$v_0$ do~$v_0$ existuje v¾dy.
Nyní si pøedstavme, ¾e oznaèujeme vrchol~$v$ pøes hranu~$uv$. To znamená, ¾e
vrchol~$u$ ji¾ musel být oznaèený. Dle indukèního pøedpokladu tedy existuje
cesta z~$v_0$ do~$u$, a tudí¾ pokud k~této cestì \uv{pøilepíme} hranu~$uv$,
dostáváme sled z~$v_0$ do~$v$, který lze v¾dy zredukovat na cestu.

\uv{$\Longleftarrow$} Sporem: Nech» existuje neoznaèený vrchol $v$ dosa¾itelný
po nìjaké cestì z~$v_0$. Uva¾me nejkrat¹í cestu $(v_0, v)$: $v_0, v_1 \dots,
v_k = v$ a vezmìme minimální~$i$ takové, ¾e~$v_i$ není oznaèený. Víme, ¾e~$i>0$
(nebo»~$v_0$ je urèitì oznaèen u¾ na zaèátku algoritmu). Tudí¾~$v_{i-1}$ je
oznaèený. Pøi oznaèení jsme ho ov¹em pøidali do fronty, tak¾e jsme ho z~fronty
museli pozdìji zase vyjmout. Pøi tom jsme ov¹em museli objevit hranu $v_{i-1}v_i$
a oznaèit vrchol~$v_i$, co¾ je spor.
\qed

Nyní tedy víme, ¾e algoritmus je správný, a máme pøedstavu o tom, jak funguje.
Podíváme-li se na~nìj podrobnìji, zjistíme, ¾e je hodnì závislý na~tom, jak si
budeme graf pamatovat. Zanedlouho zároveò zjistíme, ¾e nám reprezentace grafu
v~pamìti znatelnì ovlivní èasovou (i pamì»ovou) slo¾itost celého algoritmu.

\h{Reprezentace grafu v~pamìti}

Mìjme nìjaký orientovaný graf~$G$ s~$n$ vrcholy a $m$~hranami. Jak ho reprezentovat?

Vrcholy mù¾eme oèíslovat od~1 do~$n$. Pro ulo¾ení hran máme na~výbìr hned nìkolik zpùsobù.
Pøedvedeme si je na grafu z~následujícího obrázku:
\figure{imgn_o4.eps}{Ukázkový graf}{\epsfxsize}

\s{1. matice sousednosti}

Matice sousednosti pro graf $G$ na~$n$ vrcholech je ètvercová matice $A$ o~rozmìrech $n \times n$,
taková, ¾e $A_{i,j}$ popisuje, jestli z~vrcholu~$i$ do vrcholu~$j$ vede hrana ($A_{i,j}=1$)
nebo nikoliv ($A_{i,j}=0$).

Ná¹ graf z~obrázku vý¹e by tedy v~maticové reprezentaci vypadal takto:

$$\bordermatrix{
  & A & B & C & D\cr
A & 0 & 1 & 1 & 0\cr
B & 0 & 0 & 0 & 1\cr
C & 0 & 0 & 0 & 1\cr
D & 1 & 1 & 0 & 0\cr
}$$

S touto maticí se pracuje velmi snadno, napø. v¹echny sousedy $i$-tého vrcholu
zjistíme jednodu¹e tak, ¾e projdeme $i$-tý øádek matice a najdeme v¹echny jednièky.
Má ov¹em dvì zøejmé nevýhody: èasovou a pamì»ovou slo¾itost. Projití sousedù
jednoho vrcholu trvá v¾dy $\Theta(n)$, projití sousedù pro v¹echny vrcholy (co¾
potøebujeme v~BFS) pak trvá $\Theta(n^2)$. Velikost matice je v¾dy $n \times
n$, bez ohledu na~to, jak \uv{øídký} je graf. U grafu s mnoha vrcholy, ale
s malým poètem hran, tedy budeme zbyteènì plýtvat místem v~pamìti. Tato
reprezentace je tedy nevýhodná pøedev¹ím pro tøídy grafù, jako jsou stromy,
které mají $n-1$ hran, nebo rovinné grafy, které mají nejvý¹e $3n-6$ hran.

\s{Pozorování:} BFS s reprezentací maticí sousednosti bì¾í v~èase: $\Theta(n^2)$.

\proof
U¾ jsme si uvìdomili, ¾e ka¾dý vrchol se dostane do~fronty $Q$ nejvý¹e jednou. Pro ka¾dý vrchol ve~frontì potøebujeme projít jeho sousedy, co¾ nám trvá s~reprezentací maticí sousednosti $\Theta(n)$. Vrcholù je celkem $n$, tedy èasová slo¾itost je $\Theta(n^2)$.
\qed

\smallskip
\s{2. seznam sousedù}

V~matici sousednosti jsme museli procházet jak hrany, tak nehrany, co¾ bylo zbyteèné. Bylo by tedy výhodnìj¹í pamatovat si pro ka¾dý vrchol pouze jeho sousedy. To mù¾eme zaøídit napøíklad jedním ze~dvou následujících zpùsobù:

Uchovávejme pole indexované vrcholy tak, ¾e v~ka¾dém prvku pole je ukazatel
na~spojový seznam sousedù tohoto vrcholu. Tedy $L(v)=\{w: vw \in E(G)\}$.

Pokud se nám nebude chtít pracovat se spojovými seznamy, mù¾eme vyu¾ít
reprezentaci pomocí dvou polí. První pole~$V$ bude opìt indexované vrcholy.
V~druhém poli~$E$ budou pro ka¾dý vrchol ulo¾eni jeho sousedé. V~poli~$V$ si
pamatujeme pro ka¾dý vrchol~$i$ index do~pole~$E$, kde zaèínají jeho sousedé,
a navíc dodefinujeme, ¾e $V[n+1]=m+1$.
K sousedùm vrcholu~$i$ se pak ji¾ dostaneme snadno -- nalezneme je na pozicích
$V[i], \dots, V[i+1]-1$.

\figure{sousedi.eps}{Znázornìní polí seznamu sousedù}{40mm}

Na tuto reprezentaci u¾ staèí prostor $\Theta(n + m)$, co¾ u¾ je, na~rozdíl
od~pøedchozího kvadratického prostoru, docela pøíjemné.

\s{Pozorování:} BFS s~reprezentací seznamem sousedù bì¾í v~èase $\Theta(n+m)$.

\proof
Algoritmus zpracuje ka¾dý vrchol nejvý¹e jednou a stráví jím èas lineární
v~poètu odchozích hran, tedy $\Theta({\rm deg}^-(v))$. Èasová slo¾itost celého
algoritmu tedy èiní:
$$\Theta\left(n+\sum_{v\in V(G)} {\rm deg}^-(v)\right) = \Theta(n+m).$$
\qed

\s{3. orákulum}

Dal¹í mo¾ností reprezentace je jakési orákulum, které nám na po¾ádání øekne (spoèítá),
kam vedou hrany z~daného vrcholu. To se hodí napøíklad tehdy, pokud graf vznikl
výpoètem a nechceme plýtvat pamìtí na jeho ulo¾ení. To se hodí napøíklad u~u¾
zmínìného hlavolamu \uv{Lloydova osmièka}.

\smallskip
\s{Neorientované grafy}

Chceme-li reprezentovat neorientovaný graf, ulo¾íme ka¾dou hranu v~obou orientacích.

\h{Výpoèet vzdáleností}

Abychom mohli vyu¾ít toho, ¾e algoritmus prochází vrcholy grafu ve~vlnì,
k~výpoètu vzdáleností, doplníme do nìj dvì pomocná pole:
$D[v]$ bude øíkat, na~kolik krokù jsme se do~$v$ dostali,
$P[v]$ bude obsahovat {\I pøedchùdce} vrcholu~$v$, toti¾ vrchol~$u$,
ze~kterého jsme se do~$v$ dostali po hranì a jeho¾ $D[u]=D[v]-1$.

\smallskip
\s{Roz¹íøený algoritmus:}
\algo
\:$Q \leftarrow \{v_0\}$.
\:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
\:$D[*] \leftarrow \infty, D[v_0] \leftarrow 0$.
\:Dokud $Q \not= \emptyset $ opakujeme:
\::Vyzvedneme vrchol $u$ z~$Q$.
\::Pro ka¾dý vrchol $v$, do~kterého vede hrana z~vrcholu $u$:
\:::Je-li $Z[v]=0$:
\::::$Z[v] \leftarrow 1, D[v] \leftarrow D[u]+1, P[v] \leftarrow u$
\::::Pøidáme $v$ do~$Q$.
\endalgo

\s{Definice: {\I Fáze bìhu algoritmu}:} Ve~fázi $F_0$ je zpracováván vrchol $v_0$. Ve~fázi $F_{i+1}$ jsou zpracovávány vrcholy ulo¾ené do~fronty $Q$ bìhem fáze $F_i$.

\s{Pozorování:} Ka¾dý vrchol~$v$ dosa¾itelný z~$v_0$ se úèastní právì jedné fáze,
a to té s~èíslem~$D[v]$.

\s{Lemma:} Po zastavení BFS pro v¹echny vrcholy dosa¾itelné z~$v_0$ platí, ¾e $D[v]$
je rovno $d(v_0,v)$, toti¾ vzdálenosti (délce nejkrat¹í cesty) z~$v_0$ do~$v$.

\proof
Nejprve si uvìdomíme, ¾e kdykoliv je~$v$ oznaèen, vede do nìj z~$v_0$ nìjaký
sled délky~$v$ (indukcí, stejnì jako jsme pøed chvílí dokazovali, ¾e BFS projde
v¹echny dosa¾itelné vrcholy). Proto nemù¾e být $D[v]$ men¹í ne¾ $d(v_0,v)$.

Sporem doká¾eme, ¾e nemù¾e být ani vìt¹í. Pøedpokládejme, ¾e existuje nìjaký
\uv{¹patný} vrchol~$v$, pro který je $D[v] > d(v_0,v)$. Nech» $P$ je nìkterá z~nejkrat¹ích
cest z~$v_0$ do~$v$. Z~mo¾ných ¹patných vrcholù si vyberme takový, jeho¾ $P$ je nejkrat¹í
mo¾ná. Jeliko¾ pro vrchol~$v_0$ je zajisté $D[v_0] = d(v_0,v_0) = 0$, musí být $v$
rùzný od~$v_0$, tak¾e má na~$P$ nìjakého pøedchùdce~$u$. Pro toho ov¹em je vzdálenost
spoèítána správnì: $D[u] = d(v_0,u) = d(v_0,v)-1$.

Uva¾ujme nyní, co se stalo v~okam¾iku, kdy jsme~$D[u]$ nastavili. Tehdy jsme~$u$
ulo¾ili do fronty, po èase jsme ho z~fronty zase vytáhli a prozkoumali jsme v¹echny
vrcholy, do ní¾ vede z~$u$ hrana. Tedy i vrchol~$v$, tak¾e $D[v]$ v~tomto okam¾iku
nemù¾e být vìt¹í ne¾ $D[u]+1 = d(v_0,v)$, a~to je spor.
\qed

Víme tedy, ¾e BFS správnì spoèítá délky nejkrat¹ích cest do v¹ech vrcholù grafu.
Pomocí pøedchùdcù v~poli~$P$ mù¾eme tyto cesty dokonce snadno rekonstruovat:
pøedposledním vrcholem na nejkrat¹í cestì do~vrcholu~$v$ musí být vrchol $P[v]$,
jeho pøedchùdcem $P[P[v]]$, \dots, a¾ do~vrcholu~$v_0$.

Pøedchùdci nám tedy kódují strukturu nejkrat¹ích cest do~v¹ech vrcholù.
Mù¾eme se na nì dívat také následovnì:

\s{Definice:} Strom nejkrat¹ích cest je orientovaný strom $(W,F)$ s~mno¾inou vrcholù
$W=\{ v\in V(G) \mid \hbox{$v$ dosa¾itelný z~$v_0$} \}$
a hranami $F=\{ (P(v),v) \mid v\in W, v\ne v_0 \}$.

\s{Pozorování:} Koøenem stromu nejkrat¹ích cest je vrchol~$v_0$, cesta v~tomto
stromu z~$v_0$ do~$v$ (jednoznaènì urèená, je to strom) je pak jednou z~nejkrat¹ích
cest z~$v_0$ do~$v$ v~pùvodním grafu.

\smallskip
\s{Komponenty souvislosti}

V~neorientovaných grafech mù¾eme BFS jednodu¹e pou¾ít na nalezení komponent souvislosti.
Ji¾ víme, ¾e BFS spu¹tìné z~vrcholu~$v_0$ projde právì ty vrcholy, které jsou z~$v_0$
dosa¾itelné, co¾ jsou v~neorientovaném grafu pøesnì ty, které le¾í v~té¾e komponentì.

Staèí opakovanì spou¹tìt BFS z~dosud neoznaèených vrcholù, poka¾dé nám oznaèí
jednu komponentu.

\s{Algoritmus:}
\algo
\:Pro v¹echny vrcholy $v \in V(G)$ opakujeme:
\::Pokud je vrchol $v$ neoznaèený:
\:::Spustíme $\<BFS>(v)$ a pøiøadíme objevené vrcholy nové komponentì.
\endalgo

To, co jsme o~BFS zjistili, mù¾eme shrnout do následující vìty:

\s{Vìta:} $\<BFS>(v_0)$ v~èase $\Theta(n + m)$ spoète:
\itemize\ibull
\:vrcholy dosa¾itelné z~$v_0$
\:vzdálenosti tìchto vrcholù od~$v_0$
\:strom nejkrat¹ích cest z~$v_0$
\endlist

\>Prohledávání do~¹íøky ale není jediný algoritmus, který nìjak systematicky
prochází graf. Jak u¾ název kapitoly napovídá, budeme se zabývat je¹tì druhým
algoritmem, prohledáváním do~hloubky. Podívejme se, jak bude vypadat \dots

\h{Prohledávání do~hloubky {\I Depth-First Search -- DFS }}

Tento algoritmus neprochází graf ve~vlnì jako BFS, nýbr¾ rekurzivnì. V¾dy se
zanoøí co nejhloubìji a¾ do~listu a pak se o~kus vrátí a opìt se sna¾í zanoøit.
Vrcholy, ve kterých u¾ byl, ignoruje.

Opìt uva¾me nejdøíve graf orientovaný. Následnì si uká¾eme, ¾e v~neorientovaném grafu budou pouze malé zmìny.

Budeme pou¾ívat podobné znaèení jako u~BFS. V~poli $Z$ si budeme pamatovat, zda
jsme vrchol ji¾ nav¹tívili (hodnota 1), nebo ne (hodnota 0). Aby se nám algoritmus
lépe analyzoval, zavedeme promìnnou~$T$, která bude fungovat jako hodiny -- v~ka¾dém
kroku algoritmu se zvìt¹í o~jednièku. Do~polí $\<in>$ a $\<out>$ si budeme ukládat èas
prvního a posledního prùchodu vrcholem.

\s{Algoritmus:}

\algo
\:Inicializace: $Z[*] \leftarrow 0, T \leftarrow 1, \<in>[*] \leftarrow ?, \<out>[*] \leftarrow ?$
\:$\<DFS>(v)$:
\::$Z[v] \leftarrow 1$, $\<in>[v] \leftarrow T$, $T\leftarrow T+1$
\::Pro $w$: $vw \in E(G)$:
\:::Pokud $Z[w]=0$, zavoláme $\<DFS>(w)$
\::$out[v] \leftarrow T$, $T\leftarrow T+1$
\endalgo

\s {Vìta:} DFS($v_0$) v~èase $\Theta(m+n)$ oznaèí právì v¹echny vrcholy dosa¾itelné z~$v_0$.

\proof
Korektnost doká¾eme stejným argumentem, jako u~BFS.

V~analýze èasové slo¾itosti si pak opìt uvìdomíme, ¾e algoritmus zavoláme
na~ka¾dý vrchol nejvý¹e jednou (pak u¾ je oznaèený) a zpracováním vrcholu
strávíme èas lineární v~poètu hran, které z~nìj vedou. Celkem tedy prozkoumáme
ka¾dou hranu nejvý¹e jednou a strávíme tím konstantní èas.
\qed

Vyzkou¹ejme si DFS na grafu z~následujícího obrázku:

\figure{dfs.eps}{Znázornìní prùbìhu DFS a typù hran}{\epsfxsize}

Graf je reprezentován tak, ¾e v~ka¾dém vrcholu jsou hrany uspoøádány zleva doprava.
Èísla u~vrcholù ukazují jejich \<in> a \<out>.

Mù¾eme si v¹imnout, ¾e k~rùzným hranám se DFS chová rùznì. Po~nìkterých projde,
jiné vedou do u¾ prozkoumaných vrcholù, ale nìkdy do~takových, ze~kterých jsme
se je¹tì nevrátili, jindy do u¾ zpracovaných. Za chvíli uvidíme, ¾e mohou nastat
ètyøi rùzné situace. Nejsnáze se poznávají podle hodnot \<in> a \<out>.

\s{Pozorování:} Chod algoritmu mù¾eme popsat posloupností závorek: $(_v$ bude
znaèit \uv{vstoupili jsme do~vrcholu~$v$} (a nastavili $\<in>(v)$), $)_v$ budi¾
opu¹tìní vrcholu (nastavení $\<out>(v)$). Tato posloupnost bude správnì uzávorkovaná,
èili páry závorek se nebudou køí¾it.

\s{Klasifikace hran:} DFS dìlí hrany na následující ètyøi druhy. Hrana $uv$ je:

\itemize\ibull
\:{\I Stromová} (na na¹em obrázku plná) pokud po ní DFS pro¹lo do neoznaèeného vrcholu. V¹imnìte si,
  ¾e stromové hrany spoleènì tvoøí strom orientovaný od koøene~$v_0$. (Je to
  strom, jeliko¾ vzniká postupným pøidáváním listù.) Tomuto stromu se øíká DFS strom.
\:{\I Zpìtná} (teèkovaná) -- taková hrana vede do~vrcholu, do kterého jsme
  vstoupili, ale je¹tì jsme ho neopustili (to je vrchol, který máme pøi rekurzi na zásobníku).
  Odpovídá uzávorkování $(_v \dots (_u \dots )_u \dots )_v$.
\:{\I Dopøedná} (èárkovaná) -- vede do vrcholu, který jsme u¾ opustili, ale který je
  potomkem aktuálního vrcholu: $(_u \dots (_v \dots )_v \dots )_u$.
\:{\I Pøíèná} (èerchovaná) -- vede do vrcholu, který jsme u¾ opustili, ale který ve~stromu
  nele¾í pod aktuálním vrcholem. Musí tedy vést do vrcholù \uv{nalevo} od stromové cesty
  z~$v_0$ do~$u$. Napravo toti¾ le¾í vrcholy, které v~okam¾iku opou¹tìní~$u$ je¹tì nebyly
  prozkoumané, tak¾e hrana $uv$ by se stala stromovou. Pøíèné hrany poznáme podle
  uzávorkování $(_v \dots )_v \dots (_u \dots )_u$.
\:Jiné druhy hran nemohou existovat, probrali jsme toti¾ v¹echny mo¾nosti, v~jakém
  vztahu mohou být páry závorek $(_u )_u$ a $(_v )_v$.
\endlist
Kterého typu hrana je, mù¾eme tedy poznat podle znaèky $Z[v]$ a podle hodnot \<in> a \<out>
vrcholù $u$ a~$v$.

\s{Neorientované grafy:} V~neorientovaných grafech (ka¾dou hranu vidíme jako dvì orientované
hrany) je situace daleko jednodu¹¹í. Buïto hranu objevíme jako stromovou (a v~opaèném smìru
ji vidíme jako zpìtnou), nebo ji objevíme jako zpìtnou (a~v~opaèném smìru se jeví dopøednou).
Pøíèné hrany nemohou existovat, proto¾e k~nim opaèná hrana by byla pøíèná vedoucí zleva
doprava, co¾ víme, ¾e nenastane.

\bye
