3 \prednaska{3}{Prohledání do~¹íøky a do~hloubky}{()}
5 \h{Prohledání do~¹íøky (BFS) {\I Breadth-First Search} }
7 Jde o grafový algoritmus, který postupnì prochází v¹echny vrcholy v~dané komponentì souvislosti.
8 Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd\dots
9 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.
10 \figure{praseci-graf.eps}{Praseèí graf}{55mm}
14 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, è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á.
17 Nejprve se podívejme, jak algoritmus pracuje na orientovaném grafu. Pro neorientovaný graf funguje algoritmus analogicky, co¾ si uká¾eme pozdìji.
22 \:$Q \leftarrow \{v_0\}$.
23 \:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
24 \:Dokud $Q \not= \emptyset $ opakujeme:
25 \::Vyzvedneme vrcholy $u$ z~$Q$.
26 \::$\forall w: (u,w)\in E$:
27 \:::Je-li $Z[w]=0 \Rightarrow Z[w] \leftarrow 1$, pøidáme $w$ do~$Q$.
31 \>{\I Pozorování:} {\I BFS} se zastaví.
33 \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.)
35 \s{Lemma:} BFS($v_0$) oznaèí $v$ právì tehdy, kdy¾ existuje cesta z~$v_0$ do~$v$.
38 \uv{$\Longrightarrow$}:
39 Platí jako invariant po celou dobu bìhu algoritmu. To doká¾eme indukcí dle doby bìhu algoritmu:
41 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.
43 \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ý. Museli jsme tedy pou¾ít hranu~$v_{i-1}~v_i$ a oznaèit vrchol~$v_i$, co¾ je SPOR. \qed
45 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.
47 \h{Reprezentace grafu v~pamìti}
49 Oznaème vrcholy grafu na~následujícím obrázku písmeny A, B, C, D.
50 Pokud bychom chtìli tento graf uchovat v~pamìti poèítaèe, máme na~výbìr
51 hned nìkolik zpùsobù, jak to udìlat.
52 \figure{imgn_o4.eps}{}{\epsfxsize}
53 \s{1. matice sousednosti}
55 Matice sousednosti pro graf $G$ na~$n$ vrcholech je ètvercové pole $A$ o velikosti $n \times n$, jeho¾ prvky na
56 souøadnicích $i, j$ jsou dány následujícím pøedpisem:
58 $$ A_{i,j} = \left\{ \matrix {1 \Leftrightarrow \{i,j\} \in E \cr
59 0 \Leftrightarrow \{i,j\} \notin E \cr
63 Na~pozicích $i,j$ je jednièka, pokud v~grafu $G$ vede hrana z~vrcholu~$i$ do~vrcholu~$j$, jinak to je nula.
64 Ná¹ graf z~obrázku vý¹e by tedy v~maticové reprezentaci vypadal takto:
74 S touto maticí se pracuje velmi snadno, napø. v¹echny sousedy $i$-tého vrcholu
75 zjistíme jednodu¹e tak, ¾e projdeme $i$-tý øádek matice.
76 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.
78 \s{Pozorování:} BFS s reprezentací maticí sousednosti bì¾í v~èase: $\Theta(n^2)$.
81 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)$.
86 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ù:
88 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)\}$.
90 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é. K sousedùm vrcholu~$i$ se tedy dostaneme ji¾ snadno - nalezneme je na pozicích $V[i]~\dots~V[i+1]-1$.
91 \figure{imgn_nei.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize}
94 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é.
96 \s{Pozorování:} BFS bì¾í v~èase: $\Theta(n+m)$.
99 Algoritmus vezme ka¾dý vrchol i ka¾dou hranu do~ruky nejvý¹e jednou. Èasová slo¾itost bude tedy:
100 $$\Theta\left(n+\sum_{v\in V(G)} {\rm deg}(v)\right) = \Theta(n+m).$$
105 Dal¹í mo¾ností reprezentace je pak jakési orákulum, které nám øekne (spoèítá), kam vedou hrany z~daného vrcholu\dots To se hodí napøíklad tehdy, pokud si nepotøebujeme pamatovat celý graf, ale staèí nám naleznout sousedy nìjakého vrcholu, které orákulum jednoznaènì výpoètem doká¾e urèit. Napøíklad pøi øe¹ení známé úlohy odmìøení daného mno¾ství vody za pomocí nádob rùzných objemù mù¾eme tento zpùsob reprezentace grafu pou¾ít. Problém pøevedeme na prohledávání grafu do~¹íøky, kde vrcholùm odpovídají jednotlivé stavy. Stav øíká, kolik vody je zrovna ve které nádobì. Potom nám ji¾ staèí ze zadaného poèáteèního vrcholu (stavu) najít cestu do~cílového. Orákulum je zde vlastnì funkce, které pøedáme vrchol a ona nám vrátí v¹echny vrcholy sousední -- tedy takové stavy, ke kterým dojde, kdy¾ vyzkou¹í v¹echny mo¾nosti pøelití kapaliny z jedné nádoby do~druhé.
107 \h{Roz¹íøení algoritmu:}
109 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í:
111 V~poli $D$ bude pro ka¾dý vrchol ulo¾ena vzdálenost od~poèáteèního vrcholu.
112 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:
114 \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$.
116 \s{Roz¹íøený algoritmus:}
118 \:$Q \leftarrow \{v_0\}$.
119 \:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
120 \:$D[*] \leftarrow \infty, D[v_0] \leftarrow 0$.
121 \:Dokud $Q \not= \emptyset $ opakujeme:
122 \::Vyzvedneme vrchol $u$ z~$Q$.
123 \::Pro ka¾dý vrchol $w$, který je sousedem vrcholu $u$:
124 \:::Je-li $Z[w]=0 \Rightarrow Z[w] \leftarrow 1, D[w] \leftarrow D[u]+1, P[w] \leftarrow u$
125 \::::Pøidáme $w$ do~$Q$.
128 \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$. (Kde $d(x,y)$ je délka nejkrat¹í cesty z~$x$ do~$y$).
131 \uv{$\Longrightarrow$}:
132 Dùkaz provedeme indukcí podle $i$ (èísla fáze bìhu algoritmu).
134 První krok indukce je triviální, nebo» ve~fázi $F_0$ je oznaèen (dle definice) pouze vrchol $v_0$ a to je jediný vrchol vzdálený~0 od~$v_0$.
136 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)\leq i$, nebo» je¹tì nevíme, zda cesta $v_0, \dots, u, v$ je nejkrat¹í. Kdyby ale existovala nìjaká krat¹í, tedy délky nejvý¹e $i-1$, tak by byl vrchol $v$ objeven u¾ døíve ne¾ ve fázi $F_i$. Proto $d(v_0,v) = i$.
139 \uv{$\Longleftarrow$}: Ka¾dý dosa¾itelný vrchol padne do~nìjaké fáze (viz. minulé lemma).
142 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]$).
144 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$.
147 \s{Pozorování:} Pokud víme, ¾e $v_0, v_1, \dots, v_{k-1}, v_k$ je nejkrat¹í cesta z~$v_0$ do~$v_k$, pak $v_0,v_1,\dots,v_{k-1}$ je nejkrat¹í cesta z~$v_0$ do~$v_{k-1}$. Neboli prefix nejkrat¹í cesty je nejkrat¹í cesta.
150 Kdyby existovala krat¹í cesta z~$v_0$ do~$v_{k-1}$, pak bychom mohli zkrátit i cestu z~$v_0$ do~$v_k$.
153 \s{Pozorování:} BFS u~neorientovaného grafu projde celou komponentu souvislosti.
156 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.
159 \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.
163 \:Pro v¹echny vrcholy $v \in V(G)$ opakuj:
164 \::Pokud je vrchol $v$ neobarvený $ \Rightarrow \<BFS(v)>$.
168 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).
169 Postupnì projdeme v¹echny vrcholy od prvního k poslednímu a v¾dy pokud je vrchol neobarvený, spustíme na nìj BFS. Tak nakonec obarvíme v¹echny komponenty souvislosti. Èasová slo¾itost bude stejná jako u~samotného BFS, tedy $\Theta(n + m)$.
172 \s{Vìta:} $BFS(v_0)$ v~èase $\Theta(n + m)$ spoète:
174 \:vrcholy dosa¾itelné z~$v_0$
175 \:vzdálenosti tìchto vrcholù od~$v_0$
176 \:strom nejkrat¹ích cest z~$v_0$
179 \s{Poznámka:} Algoritmus na prohledávání do~¹íøky bude fungovat i na neorientovaném grafu. Mù¾eme si jednodu¹e pøedstavit, ¾e je to orientovaný graf, kde ka¾dá hrana má oboustrannou orientaci.
182 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
184 \h{Prohledávání do~hloubky (DFS) {\I Depth-First Search} }
186 Tento algoritmus neprochází graf ve~vlnì jako BFS, ale prochází ho 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.
188 Opìt uva¾me nejdøíve graf orientovaný. Následnì si uká¾eme, ¾e v~neorientovaném grafu budou pouze malé zmìny.
190 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.
195 \: inicializace: $Z[*] \leftarrow 0, T \leftarrow 1, \<in>[*] \leftarrow ?, \<out>[*] \leftarrow ?$
196 \: $DFS(v): Z[v] \leftarrow 1, \<in>[v] \leftarrow T|++|$
197 \:: Pro $w$: $vw \in E(G)$:
198 \::: Pokud $Z[w]=0 \Rightarrow DFS(w)$
199 \:: $out[v] \leftarrow T|++|$
202 \s {Vìta:} DFS($v_0$) v~èase $\Theta(m+n)$ oznaèí právì v¹echny vrcholy dosa¾itelné z~$v_0$.
205 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.
207 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)$.
210 \figure{img5_dfso.eps}{Graf a znázornìní prùbìhu DFS s~jednotlivými hranami:}{\epsfxsize}
212 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é}.
214 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)\}$.
216 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)$.
218 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)$.
220 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)$.
222 \s{K zamy¹lení:} Proè nemohou vést pøíèné hrany také zleva doprava?
224 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á:
226 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$.
228 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$.
230 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$.
232 Pozn: Pou¾íváme zde toto znaèení: $<>_v = <in(v), out(v)>$. Jedná se o interval objevení a opu¹tìní vrcholu $v$.
234 \s{Typy hran ($v \rightarrow w$):}
237 \:Stromové hrany \dots po nich DFS pro¹lo. $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$
238 \:Zpìtné hrany $<<>_v>_w$\dots vedou do~pøedchùdce $v$ ve~stromu. $\{(C \rightarrow A)\}$
239 \:Dopøedné hrany $<<>_w>_v$\dots vedou do~potomka. $v$ $\{(A \rightarrow D)\}$
240 \:Pøíèné hrany $<>_w<>_v$\dots vedou do~vrcholu $v$ v~sousedním podstromì, v¾dy zprava doleva. $\{(D \rightarrow A)\}$
243 \s{Pozorování:} Hrany, po~kterých DFS pro¹lo, tvoøí DFS strom.
245 \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).
247 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é}.
projects / ads1.git / blob