Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu Everything on earth can be found, if only you do not let yourself be put off searching. Philemon of Syracuse (ca. 360 BC-264 BC) pro daný graf G a vrchol s grafu je cílem • navštívit všechny vrcholy grafu dosažitelné z vrcholu s, resp. • navštívit všechny vrcholy grafu průzkum realizovat maximálně efektivně, tj. se složitostí 0(V + E) (vyhnout se opakovaným návštěvám ) jaké další informace o grafu zjistíme v průběhu průzkumu??? IB002 Algoritmy a datové struktury I Jaro 2018 299 / 390 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šírky vs do hloubky Theseus si před bludištěm uváže jeden konec nitě na strom a vsoupí dovnitř. V prvním vrcholu (křižovatce) si vybere jednu možnou cestu / hranu a projde po ní do dalšího vrcholu. Aby Theseus neměl zmatek v tom, které hrany už prošel, tak si všechny hrany, které prochází označuje křídou - a to na obou koncích. V každém vrcholu, do kterého Theseus dorazí, provede následující: ■ Pokud na zemi najde položenou nit, tak ví, že už ve vrcholu byl a že se do něj při namotávání nitě zase vrátí. Odloží tedy další prozkoumávání tohoto vrcholu na později, provede čelem vzad a začne namotávat nit na klubko. To ho dovede zpátky do předchozího vrcholu. ■ Pokud na zemi žádnou nit nenajde, tak se vydá první možnou neprošlou hranou. Pokud by taková hrana neexistovala, tak je vrchol zcela prozkoumán. V tom případě Theseus neztrácí čas a začne namotávat nit na klubko. Tím se dostane zpátky do předchozího vrcholu. Tímto postupem prozkoumá celé bludiště a nakonec se vrátí do výchozího vrcholu.6 Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka HUB EQ HH 91 Jaro 2018 300 / 390 IB002 Algoritmy a datové struktury I Průzkum grafu do šírky vs do hloubky implementace křída proměnná označující jestli jsme hranu prošli klubko položená niť vyznačuje cestu z výchozího do aktuálního vrcholu, cestu si pamatujeme jako posloupnost vrcholů na této cestě. Pro uložení cesty použijeme zásobník. Odmotávání nitě odpovídá přidání vrcholu do zásobníka. Namotávání nitě při návratu zpět odpovídá odebrání vrcholu ze zásobníku. IB002 Algoritmy a datové struktury I Jaro 2018 301 / 39 Průzkum grafu do šírky vs do hloubky Tento průchod (prohledánígrafu) si můžeme představit tak, že se do výchozího vrcholu postaví miliarda trpaslíků a všichni naráz začnou prohledávat graf. Když se cesta rozdělí, tak se rozdělí i dav řítící se hranou. Předpokládáme, že všechny hrany jsou stejně dlouhé. Graf prozkoumáváme „po vlnách". V první vlně se všichni trpaslíci dostanou do vrcholů, dokterých vede z výchozího vrcholu hrana. V druhé vlně se dostanou do vrcholů, které jsou ve vzdálenosti 2 od výchozího vrcholu. Podobně v k-té vlně se všichni trpaslíci dostanou do vrcholů ve vzdálenosti k od výchozího vrcholu. Kvůli těmto vlnám se někdy průchodu do šířky říka algoritmus vlny. 7 implementace V počítači vlny nasimulujeme tak, že při vstupu do nového vrcholu uložíme všechny s ním sousedící vrcholy do fronty. Frontu průběžně zpracováváme. Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka HUB EQ HH 91 Jaro 2018 302 / 390 IB002 Algoritmy a datové struktury I Průzkum do šířky - strategie cílem je prozkoumat všechny vrcholy dosažitelné z daného iniciálního vrcholu s ■ postupujeme od iniciálního vrcholu s po vrstvách ■ nejdříve prozkoumáme všechny vrcholy dosažitelné z s po 1 hraně ■ pak všechny vrcholy dosažitelné po 2 hranách, po 3 hranách atd. ■ pro manipulaci s vrcholy používáme prioritní frontu Q ■ v £ Q právě když byl dosažen (objeven) ale ještě nebyl prozkoumán IB002 Algoritmy a datové struktury I Jaro 2018 304 / 39 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do šířky - příklad Q: S Q: AD Q: DC Q: CBE C D Q: BE C D Q: E C D Q: 0 IB002 Algoritmy a datové struktury I Jaro 2018 305 / 390 Průzkum do šířky - atributy vrcholu v.color ■ v průběhu výpočtu je vrchol postupně objeven (je zařazen do fronty) a prozkoumán (všechny sousedící vrcholy jsou objeveny) ■ vrchol má černou barvu právě když je dosažitelný z iniciálního vrcholu a byl již prozkoumán ■ vrchol má šedivou barvu právě když je dosažitelný z iniciálního vrcholu, byl již objeven, ale nebyl ještě prozkoumán ■ vrchol má bílou barvu právě když není dosažitelný z iniciálního vrcholu anebo ještě nebyl objeven v.7t ■ vrchol, ze kterého byl v objeven v.d ■ délka (počet hran) cesty z s do v, na které byl v objeven (= délka nej kratší cesty z s do v ) IB002 Algoritmy a datové struktury I Jaro 2018 306 / 39 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do šířky - implementace BFS(G,s) 1 foreach wGľ \ {s} 2 do u.color white] u.d oo; u.tt s s.color gray] s.d 0; s.tt Nil 4 Q^tt 5 Enqueue(Q, s) e while Q ŕ 0 do 7 10 11 12 13 U 15 od Nil od i/ <— Dequeue(Q) foreach i; G Adj[u] do if v.color — white then v.color gray i?.d i/.d + 1 v.7t i/ Enqueue(Q, v) fi u.color 6/acA: od IB002 Algoritmy a datové struktury I Jaro 2018 307 / 39C BFS a nejkratší cesty v neohodnoceném grafu Nejkratší cesta v neohodnoceném grafu Délka nejkratší cesty z s do v, značíme ô(s,v), je definována jako minimální počet hran na cestě z s do v. Když neexistuje žádná cesta z s do v, tak ô(s,v) — oo. Nejkratší cestou z 5 do i; je každá cesta z s do v která má S(s,v) hran. IB002 Algoritmy a datové struktury I Jaro 2018 310 / 390 BFS a nejkratší cesty v neohodnoceném grafu Věta 12 Necht G — (V, E) je graf a s £ V jeho vrchol, na které aplikujeme algoritmus BFS. Pak po ukončení výpočtu pro každý vrchol v E V platí v.d — 5(5, v) dokážeme indukcí podle hodnoty v.d □ vrchol s má s.d — 0 a nejkratší cesta z s do s má nula hran B předpokládejme, že pro všechny vrcholy s hodnotou v.d < k je v.d délka nejkratší cesty do v Q potřebujeme ukázat indukční krok a to je, že každý vrchol v s v.d = k + 1 leží ve vzdálenosti k + 1 od s ■ pokud ne, tak existuje kratší cesta z s do v a nechť (w,v) je poslední hrana na tého cestě ■ w.d < k ■ potom se ale měl algoritmus při zpracovávání vrcholu w podívat na hranu (w,v) a nastavit hodnotu v.d na w.d+ 1 ■ w.d + 1 < k + 1, spor IB002 Algoritmy a datové struktury I Jaro 2018 311 / 39 Průzkum grafů a grafová souvislost Průzkum do šířky BFS strom a nejkratší cesty algoritmus BFS definuje přes atributy tt graf předchůdců formálně: pro graf G = (V, E) a iniciál ní vrchol s je graf předchůdců Gn — {y^^E^) definovaný předpisem Vn = {veV | v.7t ŕ Nil} U {s} En = {(v.ir,v) |dG14\WÍ graf předchůdců se nazývá BFS strom ■ BFS strom je kostrou grafu ■ pro každý vrchol v G Vn obsahuje BFS strom jedinou cestu z s do v, která je současně nejkratší cestou z s do v IB002 Algoritmy a datové struktury I graf a jeho dva různé BFS stromy Jaro 2018 312 / 390 Aplikace a algoritmy využívající BFS ■ Peer to Peer Networks ■ Crawlers in Search Engines ■ Social Networking Websites - hledání osob ve vzdálenosti nejvíce k ■ GPS navigační systémy ■ broadcasting ■ garbage collection ■ Fordův Fulkersonův algoritmus pro hledání maximálního toku v síti ■ testování bipartitnosti IB002 Algoritmy a datové struktury I Jaro Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum grafu do hloubky- motivace pořadí, v němž BFS zkoumá vrcholy, netvoří souvislou cestu v grafu IB002 Algoritmy a datové struktury I Jaro 2018 317 / 39C Průzkum grafů a grafová souvislost Průzkum do hloubky Formulace problému ■ průzkum do šírky a stejně tak i průzkum do hloubky je možné použít buď k prozkoumání té části grafu, která je dosažitelná z iniciálního vrcholu, anebo k prozkoumání celého grafu ■ průzkum se dá aplikovat na orientované i neorientované grafy ■ prezentace průzkumu do hloubky předpokládá, že • vstupem je orientovaný graf a • cílem je prozkoumat celý graf IB002 Algoritmy a datové struktury I Jaro 2018 318 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum do hloubky - strategie ■ na začátku výpočtu a vždy po dokončení průzkumu vybereme jeden z dosud neprozkoumaných vrcholů a zvolíme ho za nový iniciální vrchol ■ označ iniciální vrchol jako objevený ■ vyber neprozkoumanou hranu (u,v), která vychází z naposledy objeveného vrcholu u, a když její koncový vrchol v ještě nebyl prozkoumán, tak ho označ jako objevený ■ když všechny hrany vycházející z naposledy objeveného vrcholu u byly prozkoumány, tak ukonči průzkum vrcholu u a pokračuj vrcholem, ze kterého byl vrchol u objeven ■ průzkum končí když jsou prozkoumány všechny vrcholy dosažitelné z iniciálního vrcholu ■ pro manipulaci s vrcholy používáme zásobník IB002 Algoritmy a datové struktury I Jaro 2018 319 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum grafu do hloubky - příklad IB002 Algoritmy a datové struktury I Jaro 2018 320 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum do hloubky - atributy vrcholu v.color ■ vrchol má černou barvu právě když je dosažitelný z iniciálního vrcholu a byl již prozkoumán, tj. byly prozkoumány všechny hrany vycházející z vrcholu ■ vrchol má šedivou barvu právě když je dosažitelný z iniciálního vrcholu, byl již objeven, ale nebyl ještě prozkoumán ■ vrchol má bílou barvu právě když není dosažitelný z iniciálního vrcholu anebo ještě nebyl objeven v.7t vrchol, ze kterého byl v objeven v.d časová značka, která zaznamenává čas první návštěvy vrcholu (discovery time) v.f časová značka, která zaznamenává čas ukončení průzkumu vrcholu (finishing time) IB002 Algoritmy a datové struktury I Jaro 2018 321 / 39 Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum do hloubky - implementace DFS(G) 1 foreach u E V do u.color white] u.tt Nil od 2 time 0 s foreach u EV do 4 if u.color = white then Dfs_Visit(G, u) fi od DFS_Visit(G» 1 time time + 1 2 u.d time 3 u.color gray 4 foreach v G Ad/[^] do 5 if v.color — white then i;.7r ^— 1/ 6 Dfs_Visit(G, v) fi od 7 u.color s time time + 1 s u.f time IB002 Algoritmy a datové struktury I Jaro 2018 322 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky Průzkum do hloubky - iterativní implementace 1 5^0 2 S.push{u) 3 time time + 1; u.d time 4 u.color gray 5 while S ^ 0 do 6 u <— S.popi) 7 if existuje hrana i?) taková, že v.color = white 8 then S.push{u) 9 S.push{y) 10 v.color gray 11 v.7t i/ 12 time time + 1; v.d time i5 else u.color time time + 1; u.f time fi od IB002 Algoritmy a datové struktury I Jaro 2018 324 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky DFS strom analogicky jako u BFS definují atributy .tt graf předchůdců protože prohledáváme celý graf, který nemusí být nutně souvislý, graf předchůdců je DFS les, který se skládá z DFS stromů Gw = (V, En) En — {(v.tt, v) | v G V a v.tt ^ Nil} IB002 Algoritmy a datové struktury I Jaro 2018 325 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky DFS - vlastnosti časových značek časové značky, které DFS přiřadí vrcholům grafu, obsahují informace o struktuře grafu a DFS stromů pro každý vrchol u platí u.d < u.f s každým vrcholem u je asociovaný interval [u.d, u.f] časové značky určují uspořádání vrcholů preoder uspořádání podle značky .d (discovery time) v rostoucím pořadí postorder uspořádání podle značky ./ (finishing time) v rostoucím pořadí reverse postorder uspořádání podle značky ./ (finishing time) v klesajícím pořadí IB002 Algoritmy a datové struktury I Jaro 2018 326 / 390 Průzkum grafů a grafová souvislost Průzkum do hloubky DFS - klasifikace hran stromová hrana (tree edge) je hrana (u,v) obsažená v DFS lese při průzkumu hrany je vrchol v bílý u.d < v.d < v. f < u.f zpětná hrana [back edge) je hrana (u,v) která spojuje vrchol u s jeho předchůdcem v v DFS stromu při průzkumu hrany je vrchol v šedivý v.d < u.d < u.f < v. f dopředná hrana ( forward edge) je hrana (u,v), která nepatří do DFS stromu a která spojuje vrchol u s jeho následníkem v DFS stromu při průzkumu hrany je vrchol v černý u.d < v.d < v.f < u.f příčná hrana (cross edge) všechny ostatní hrany při průzkumu hrany je vrchol v černý v.d < v.f < u.d < u.f všechny hrany v neorientovaném grafu jsou buď stromové anebo zpětné ■ra 2g wm 22 D Jar°2018 329 /390 IB002 Algoritmy a datové struktury I Průzkum grafů a grafová souvislost Průzkum do hloubky Časové značky a klasifikace hran - příklad stromové hrany jsou zvýrazněné, zpětné hrany jsou označeny písmenem B, dopředně písmenem F a příčné písmenem C ■ra 2g wm 22 D Jar°2018 330 /390 IB002 Algoritmy a datové struktury I Průzkum grafů a grafová souvislost Průzkum do hloubky Aplikace a algoritmy využívající DFS ■ topologické uspořádání ■ komponenty souvislosti ■ artikulace a mosty ■ testování planarity ■ hledání cesty v bludišti ■ generování bludiště IB002 Algoritmy a datové struktury I Jaro 2018 331 / 390