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

\input ../lecnotes.tex

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

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

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...
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í nejkra¹í cesty mezi dvìma vrcholy v~grafu.
\figure{praseci-graf.eps}{Praseèí graf}{55mm}


\s{Popis algoritmu:}
Na zaèátku si 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, èi nikoli. Pro vrchol $v_0$ si tedy dosazením jednièky zapamatujeme, ¾e je ji¾ nav¹tívený. V~dal¹ím kroku pak zkoumáme frontu $Q$: pokud není prázdná, vezmeme z~ní první vrchol a podíváme se na~v¹echny jeho sousedy $w$. Pokud je¹tì nejsou oznaèené (tedy $Z[w]=0$), tak je oznaèíme (zapamatujeme si, ¾e je pøedáváme ke zpracování a u¾ je nemáme znovu nav¹tìvovat) a pøidáme je do~fronty k~následnému zpracování. Takto cyklus 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 vrcholy $u$ z~$Q$.
\::$\forall w: \{u,w\} \in E$:
\:::Je-li $Z[w]=0 \Rightarrow Z[w] \leftarrow 1$, pøidáme $w$ do~$Q$.
\endalgo


\>{\I 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$, tak máme hledanou cestu z~$v_0$ do~$v$.

\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, \dots, u, v$. Pøedposlední vrchol na~této cestì (vrchol $u$) musí být oznaèený. Vrchol $u$ se dostane do~fronty, pak je z~ní vybrán a tím se zpracuje i vrchol $v$, co¾ je SPOR. \qed

Nyní tedy víme, ¾e je algoritmus 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}

Oznaème vrcholy grafu na~následujícím obrázku písmeny A, B, C, D.
Pokud bychom chtìli tento graf uchovat v~pamìti poèítaèe, máme na~výbìr
hned nìkolik zpùsobù, jak to udìlat.
\figure{img1_stvorec.eps}{}{\epsfxsize}

\s{1. matice sousednosti}

Matice sousednosti pro graf $G$ na~$n$ vrcholech je ètvercové pole $A$ o velikosti $n \times n$, jeho¾ prvky na
souøadnicích $i, j$ jsou dány následujícím pøedpisem:

$$ A_{i,j} = \left\{ \matrix {1 \Leftrightarrow \{i,j\} \in E  \cr
                                0 \Leftrightarrow \{i,j\} \notin E \cr                                  
                                }
\right.$$

Na~pozicích $i,j$ je jednièka, pokud v~grafu $G$ vede hrana z~vrcholu $i$ do~vrcholu $j$, jinak to je nula.
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 & 1 & 0 & 1 & 1\cr
C & 1 & 1 & 0 & 1\cr
D & 0 & 1 & 1 & 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.
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

\s{2. seznam sousedù}

V~matici sousednosti jsme tedy 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ù:

Budeme si uchovávat pole indexované vrcholy, pøièem¾ v~ka¾dém prvku pole bude 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í: polem vrcholù $V(G)$, jeho¾ prvky postupnì pro ka¾dý vrchol udávají index zaèátku odpovídajícího úseku v~druhém poli $E(G)$, ve~kterém jsou ulo¾eni jeho sousedé. Pak tedy hrany z~vrcholu $i$ \uv{bydlí} v~poli $E$ a~to na~pozicích $V[i] \dots V[i+1]-1$.
\figure{img4_susedia.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize}


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

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

\proof
Algoritmus vezme ka¾dý vrchol i ka¾dou hranu do~ruky nejvý¹e jednou. Èasová slo¾itost bude tedy:
$$\Theta(n+\sum_{v\in V(G)} {\rm deg}(v)) = \Theta(n+m).$$
\qed

\s{3. orákulum}

Dal¹í mo¾ností reprezentace je pak jakési orákulum, které nám øekne (spoèítá), kam vedou hrany z~daného vrcholu\dots

\h{Roz¹íøení algoritmu:}

Abychom mohli vyu¾ít toho, ¾e algoritmus prochází vrcholy grafu ve~vlnì, a jiných hezkých vlastností, tak si dodefinujeme následující oznaèení:

V~poli $D$ bude pro ka¾dý vrchol ulo¾ena vzdálenost od~poèáteèního vrcholu.
V~poli $P$ si budeme pro ka¾dý vrchol pamatovat jeho pøedchùdce. Dále budeme vyu¾ívat fáze bìhu algoritmu, které budou simulovat onu vlnu:

\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{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 $w$, který je sousedem vrcholu $u$:
\:::Je-li $Z[w]=0 \Rightarrow Z[w] \leftarrow 1, D[w] \leftarrow D[u]+1, P[w] \leftarrow u$
\::::Pøidáme $w$ do~$Q$.
\endalgo

\s{Lemma:} Na~konci BFS pro v¹echny vrcholy dosa¾itelné z~$v_0$ platí, ¾e vrchol $v$ byl zpracován ve~fázi $F_i$ právì tehdy, kdy¾ vzdálenost $v_0$ a $v$ (délka nejkrat¹í cesty z~$v_0$ do~$v$) je rovna $i$. Formálnì zapsáno: $v \in F_i \Leftrightarrow d(v_0,v) = i$.

\proof
\uv{$\Longrightarrow$}: 
Dùkaz provedeme indukcí podle $i$ (èísla fáze bìhu algoritmu).

První krok indukce je triviální, nebo» ve~fázi $F_0$ je oznaèen (dle definice) pouze vrchol $v_0$ a ten je od vrcholu $v_0$ vzdálen 0. 

Pokud je vrchol $v$ zpracováván ve~fázi $F_i$, pak musel být zaøazen do fronty bìhem fáze $F_i-1$ jako soused nìjakého vrcholu $u$. Pro vrchol $u$ mù¾eme pou¾ít indukèní pøedpoklad, tedy ¾e délka nejkrat¹í cesty z $v_0$ do~$u$ je $d(v_0,u)=i-1$. Pak tedy $d(v_0,v)=i$. 

\uv{$\Longleftarrow$}: Ka¾dý dosa¾itelný vrchol padne do~nìjaké fáze (viz. minulé lemma).
\qed

Ji¾ tedy víme, ¾e vrchol $v_i$, jeho¾ vzdálenost od~vrcholu $v_0$ je $i$, bude zpracován v~$i$-té fázi. Jak ale po~skonèení algoritmu zjistíme, ve které fázi byl zpracován, neboli jak je vzdálený od~startovního vrcholu? Tato informace je právì ulo¾ena v~poli $D$ s indexem $i$ (v~$D[i]$).

Zároveò nás mù¾e zajímat, jak bychom nejkrat¹í cestu z~$v_0$ do~$v_i$ rekonstruovali. Pro tento úèel jsme si zavedli pole $P$. Nejkrat¹í cesta z~$v_0$ do~$v_i$ bude v~obráceném poøadí vypadat: $v_i, P[v_i], P[P[v_i]], P[P[P[v_i]]], \dots, v_0$.


\s{Pozorování:} $v_0v_1,...,v_{k-1}$ je nejkrat¹í cesta z~$v_0$ do~$v_{k-1}$


\s{Pozorování:} BFS u~neorientovaného grafu projde celou komponentu souvislosti.

\proof
Víme, ¾e BFS($v_0$) oznaèí $v$ právì tehdy, kdy¾ existuje cesta z~$v_0$ do~$v$. V~neorientovaném grafu existuje cesta z~$v_0$ do~právì v¹ech vrcholù, které jsou ve~stejné komponentì souvislosti jako $v_0$. Pokud tedy spustíme BFS na~$v_0$, tak se postupnì projdou v¹echny vrcholy této komponenty souvislosti.
\qed

\s{Pozorování:} Pokud BFS postupnì spou¹tíme na~dosud neobarvené vrcholy v~ neorientovaném grafu, nalezneme nakonec v~èase $\Theta(n+m)$ v¹echny komponenty souvislosti.

\proof
Ka¾dým spu¹tìním na~dosud neobarvený vrchol neorientovaného grafu obarvíme právì jednu komponentu souvislosti (tu, ve~které je tento vrchol). Jeliko¾ postupnì projdeme v¹echny vrcholy, obarvíme nakonec také v¹echny komponenty souvislosti. Èasová slo¾itost bude stejná jako u~samotného BFS, tedy $\Theta(n + m)$.
\qed

\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 (DFS) {\I Depth First Search} }

Tento algoritmus neprochází graf ve~vlnì jako BFS, ale prochází graf 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.

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. Pøi ka¾dém nalezení nového vrcholu, èi jeho opu¹tìní, pak tuto promìnnou zvý¹íme o~1. V~poli $\<in>$ a $\<out>$ bude è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, tak rozdìluje hrany do~4 skupin:

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

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

Jedinì 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$ jako zpìtnou. Pro rozpoznání je dùle¾ité, ¾e vrchol $w$ byl ji¾ objeven, ale je¹tì ne opu¹tìn.

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$ jako 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ì.

Posledním typem hran je 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$.

\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 èas 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{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).

\bye