Grafy: Prepsani casti o BFS

[ads1.git] / 3-grafy / 3-grafy.tex

\input ../lecnotes.tex

\prednaska{3}{Prohledání do~¹íøky a do~hloubky}{}

\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 s~mno¾inou vrcholù
$W=\{ v\in V(G) \mid \hbox{$v$ dosa¾itelný z~$v_0$} \}$
a hranami $\{ (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¾ ho prochází
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). Navíc promìnná~$T$ bude znaèit dobu bìhu algoritmu - tedy jakési \uv{hodiny}. Pøi ka¾dém nalezení nového vrcholu èi jeho opu¹tìní tuto promìnnou zvý¹íme o~1. Do~polí $\<in>$ a $\<out>$ si budeme ukládat èas (prvního) nalezení a opu¹tìní vrcholu.

\s{Algoritmus:}

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

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

\proof
Nejdøíve je potøeba dokázat, ¾e pokud je vrchol $v$ dosa¾itelný z~vrcholu $v_0$, tak jej DFS oznaèí. Dùkaz bude podobný jako u~BFS.

V analýze èasové slo¾itosti si pak opìt uvìdomíme, ¾e algoritmus vezme ka¾dý vrchol i hranu do~ruky právì jednou, tak¾e èasová slo¾itost bude $\Theta(n + m)$.
\qed

\figure{img5_dfso.eps}{Graf a znázornìní prùbìhu DFS s~jednotlivými hranami:}{\epsfxsize}

Mù¾eme si v¹imnout, ¾e jak DFS prochází graf, rozdìluje hrany do~4 skupin: hrany {\I stromové, zpìtné, dopøedné a pøíèné}.

Jedinì {\I stromové} hrany jsou takové, ¾e se po~nich DFS opravdu vydá. Vedou toti¾ do~vrcholu, který nebyl dosud objeven. V~ukázkovém grafu to jsou hrany: $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$.

Pokud algoritmus objeví z~vrcholu $v$ hranu do~ji¾ døíve nav¹tíveného vrcholu $w$ a zároveò platí, ¾e $w$ je ve~stejném podstromu jako $v$, tak nazveme hranu $vw$ {\I zpìtnou}. Pro rozpoznání je dùle¾ité, ¾e vrchol $w$ byl ji¾ objeven, ale je¹tì ne opu¹tìn. V~ukázkovém grafu se jedná o hranu: $(C \rightarrow A)$.

Kdy¾ pøi prohledávání sousedù vrcholu $v$ narazíme na~vrchol $w$, který jsme ji¾ nav¹tívili, a to v~podstromì vrcholu $v$, tak nazveme hranu $vw$ {\I dopøednou}, nebo» vede z~$v$ do~jeho potomka. Platí tedy, ¾e jsme nejdøíve objevili vrchol $v$, potom vrchol $w$, pak jsme vrchol $w$ opustili a nyní jsme na~nìj znovu narazili po~dopøedné hranì. V~ukázkovém grafu hrana: $(A \rightarrow D)$.

Posledním typem hran je {\I pøíèná} hrana. Ta vede do~vrcholu v~sousedním podstromì zprava doleva. V~tomto pøípadì jsme tedy nejdøíve objevili vrchol $w$, ten jsme následnì opustili a a¾ pak jsme objevili vrchol $v$. V~ukázkovém grafu to je hrana: $(D \rightarrow C)$.

\s{K zamy¹lení:} Proè nemohou vést pøíèné hrany také zleva doprava?

K~rozpoznávání typù hran se nám tedy velmi hodí pole $\<in>$ a $\<out>$, ve~kterých si pamatujeme èasy objevení a opu¹tìní vrcholu. Podle toho, jak se intervaly objevení a opu¹tìní obou vrcholù pøekrývají, mù¾eme jednoznaènì rozhodnout, o jaký typ hrany se jedná:

U~zpìtných hran je poøadí: $\<in>(w)$, $\<in>(v)$, $\<out>(v)$, $\<out>(w)$. Intervaly do~sebe budou zanoøené takto: $<<>_v>_w$.

U~dopøedných hran je poøadí: $\<in>(v)$, $\<in>(w)$, $\<out>(w)$, $\<out>(v)$. Intervaly do~sebe budou zanoøené takto: $<<>_w>_v$.

U~pøíèných hran je poøadí: $\<in>(w)$, $\<out>(w)$, $\<in>(v)$, $\<out>(v)$. Intervaly do~sebe budou zanoøené takto: $<>_w<>_v$.

Pozn: Pou¾íváme zde toto znaèení: $<>_v = <in(v), out(v)>$. Jedná se o interval objevení a opu¹tìní vrcholu $v$.

\s{Typy hran ($v \rightarrow w$):}

\itemize\ibull
\:Stromové hrany \dots po nich DFS pro¹lo. $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$
\:Zpìtné hrany $<<>_v>_w$\dots vedou do~pøedchùdce $v$ ve~stromu. $\{(C \rightarrow A)\}$
\:Dopøedné hrany $<<>_w>_v$\dots vedou do~potomka. $v$ $\{(A \rightarrow D)\}$
\:Pøíèné hrany $<>_w<>_v$\dots vedou do~vrcholu $v$ v~sousedním podstromì, v¾dy zprava doleva. $\{(D \rightarrow A)\}$
\endlist

\s{Pozorování:} Hrany, po~kterých DFS pro¹lo, tvoøí DFS strom.

\s{Pozorování:} Intervaly ($\<in>(v)$, $\<out>(v)$) $\forall v \in V(G) $ tvoøí dobré uzávorkování. (Intervaly synù disjunktnì vyplòují otce $\Rightarrow$ intervaly se nemohou køí¾it).

Nakonec si je¹tì uvìdomme, jak bude vypadat prohledávání do~hloubky na~neorientovaném grafu. Algortimus bude úplnì stejný, jenom se nám zredukuje poèet typù hran na~dvì: {\I stromové} a~{\I zpìtné}. Ani {\I dopøedné} ani {\I pøíèné} nebudou existovat, nebo» se z~{\I pøíèných} stanou {\I stromové} a z~{\I dopøedných zpìtné}.

\bye