8 Procházení grafu a odvozené úlohy Nyní se hlouběji podíváme na grafy z programátorské perspektivy: podíváme se na obecné schéma procházení grafu, které je základem mnoha užitečných algoritmů na grafech. Poté se hlouběji zaměříme na dvě specifické grafové úlohy - hledání nejkratší cesty a minimální kostry. Stručný přehled lekce * Obecné schéma procházení grafem a jeho varianty. * Nejkratší cesta v grafu a Dijkstrův algoritmus. * Minimální kostra grafu a její základní algoritmy. Petr Hliněný, Fl MU Brno, 2014 1/24 Fl: IB000: Procházení grafu 8.1 Jak obecně projít souvislý graf Metoda 8.1. Schéma algoritmu pro procházení grafem Pro vytvoření co nejobecnějšího schématu si pomůžeme následujícími: • Vrchol grafu: má stavy ... c * iniciační - dostane na začátku, * nalezený - implicitní stav poté, co jsme jej přes některou hranu nalezli (a odložili ke zpracování později), * zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející, * (příp. ještě stav „post-zpracovaný", po dokončení všech následníků).c • Úschovna: je pomocná datová struktura (množina s dodatečnými atributy), udržuje odložené, tj. nalezené a ještě nezpracované vrcholy, spolu s dodatečnou specifickou informací, c • Postup procházení: zjednodušeně lze říci, že * nalézáme z vybr. vrcholů jejich sousedy, ukládáme je do úschovny a c * pak zase vybíráme a nalézáme dále dokola, až je vše projito. Petr Hliněný, Fl MU Brno, 2014 2/24 Fl: IB000: Procházení grafu * nalézáme z vybr. vrcholů jejich sousedy, ukládáme je do úschovny a c * pak zase vybíráme a nalézáme dále dokola, až je vše projito. u c • Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu. • V prohledávaných vrcholech a hranách se volitelně provádějí dodatečné programové akce pro prohledání a zpracování našeho grafu. Petr Hliněný, Fl MU Brno, 2014 3/24 Fl: IB000: Procházení grafu Algoritmus 8.2. Generické procházení souvislé komponenty G grafu • Vstup: Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus případné ohodnocení, c • Vybereme lib. počátek prohledáváním G V (G); úschovna U ^{u}. c • Dokud ř7 ^ 0, opakujeme: * Zvolíme libovolně v G U; odebereme U <—U \ {v}. (!) * Pokud stav(u) = zpracovaný, jdeme zpět na start cyklu. (*) * Případně provedeme libovolnou akci ZPRACUJ(v). c * Pro všechny hrany / G E (G) vycházející z v provedeme: - Nechť w je druhý konec hrany / = vw; - pokud stav(io) ^ zpracovaný, odložíme U <— U U {w}. (**)□ * sta v (u) <— zpracovaný; na start cyklu, c • Souvislý G je celý prohledaný a zpracovaný. Pozor, všimněte se, že v bodě (**) obecně dochází k násobnému ukládání, což v praktické implementaci často obejdeme pouhou změnou „odloženého stavu". Petr Hliněný, Fl MU Brno, 2014 4/24 Fl: IB000: Procházení grafu Některé implementace procházení grafu Jak je vlastně proveden krok (!); „zvolíme libovolně v £ U" ? Právě tato volba je klíčová pro výslednou podobu projití grafu G: • Procházení „do šířky", BFS- úschovna U je implementovaná jako fronta, neboli je voleno v G U od prvních vrcholů vložených do úschovny, c • Procházení „do hloubky", DFS - úschovna U je implementovaná jako zásobník, neboli je voleno v G U od později vložených do úschovny. (Opakované vložení vrcholu v do U jej posune na vršek zásobníku.) c • Na obrázku si názorně ukážeme, jaký efekt má volba úschovny na výsledný výběr „objevitelských" hran v průchodu grafem: BFS ("fifo") u DFS ("lifo") u Petr Hliněný, Fl MU Brno, 2014 5/24 Fl: IB000: Procházení grafu Později v této lekci uvedeme tyto dva konkrétní, staré a dobře známé algoritmy přímo založené na prohledávání grafu: • Dijkstrův algoritmus pro nej kratší cestu - z úschovny vybíráme vždy vrchol nejbližší (dosud určenou celkovou vzdáleností) k počátečnímu u. c • Jarníkův algoritmus pro minimální kostru - z úschovny vybíráme vždy vrchol nejbližší (délkou hrany) ke kterémukoliv již zpracovanému vrcholu. Poznámka: Jarníkův algoritmus se ve světové literatuře se obvykle připisuje Američanu Primovi, který jej však objevil a publikoval až skoro 30 let po Jarníkovi. Petr Hliněný, Fl MU Brno, 2014 6/24 Fl: IB000: Procházení grafu * Konkrétní ukázky BFS a DFS Příklad 8.3. Ukázka průchodu následujícím grafem do šířky z vrcholu a. f -----* e ' ~~ ! N ' / ^ ^ s 9 -------i j d ^ - ~ - - - - -t - - * n / t ' \ / \ / a ®-----■* 6 Petr Hliněný, Fl MU Brno, 2014 7/24 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2014 8/24 Fl: IB000: Procházení grafu Příklad 8.4. Ukázka průchodu předchozím grafem do hloubky z vrcholu a. Petr Hliněný, Fl MU Brno, 2014 9/24 Fl: IB000: Procházení grafu 8.2 Vzdálenost v grafu Definice 8.5. Vzdálenost dc(u,v) dvou vrcholů u, v v grafu G je dána délkou nej kratší cesty mezi u a v v G. Pokud cesta mezi u,v neexistuje, je vzdálenost definována dc(u,v) = oo. c Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme překonat, pokud se chceme dostat z u do v. Speciálně dc(u,u) — 0. dG(u,v) = 2 Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) = dc(v,u). Tvrzení 8.6. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: yu,v,wEV(G) : do(u,v) + do(v,w) > do(u,w). Petr Hliněný, Fl MU Brno, 2014 10/24 Fl: IB000: Procházení grafu BFS a zjištění vzdálenosti Jak nejsnadněji určíme vzdálenost v grafu? Stačí si povšimnout hezkých vlastností procházení grafu do šířky. Věta 8.7. Algoritmus procházení grafu do šířky lze použít pro výpočet grafové vzdálenosti z daného vrcholu u. c • Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu u přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu v přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého byl nalezen, c Důkaz se opírá o následující tvrzení: * Nechť u,v,w jsou vrcholy souvislého grafu G takové, že dc(u,v) < cLg{u,w). Pak při algoritmu procházení grafu G do šírky z vrcholu u je vrchol v nalezen dříve než vrchol w. c Poté přirozeně postupujeme indukcí podle vzdálenosti dc(u,v). .. □ Petr Hliněný, Fl MU Brno, 2014 11/24 Fl: IB000: Procházení grafu 8.3 Hledání nejkratší cesty Definice: Vážený graf je graf G spolu s ohodnocením w hran reálnými čísly w : E{G) -+ R. Kladně vážený graf (G,w) je takový, že w(e) > 0 pro všechny hrany e. c Definice 8.8. (vážená vzdálenost) Mějme (kladně) vážený graf (G,w). Váženou délkou cesty P je d%(P) = Y w(e). Váženou vzdáleností v (G,w) mezi dvěma vrcholy u,v pak je (Íq(u, v) = min{(i^(P) : P je cesta s konci u, v} .c Tvrzení 8.9. Vážená vzdálenost v nezáporně vážených grafech (i orientovaných grafech) splňuje trojúhelníkovou nerovnost. Petr Hliněný, Fl MU Brno, 2014 12/24 Fl: IB000: Procházení grafu Příklad 8.10. Podívejme se na následující ohodnocený graf (čísla u hran udávají jejich váhy-délky.) c Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi b, c. Co ale mezi a,b?n Je jejich vzdálenost 6? Kdepak, vzdálenost a, b je 5, její cesta vede po „horních" vrcholech, jak je vyznačeno. Povšimněte si, že tento příklad zároveň ukazuje, že postup prohledáváním do šířky není korektní pro hledání vzdáleností ve váženém grafu. □ Petr Hliněný, Fl MU Brno, 2014 13/24 Fl: IB000: Procházení grafu Problém nejkratší cesty Jedná se patrně o nejznámější „grafový" problém v praktických aplikacích, jenž nalezneme od vyhledávání dopravních spojení, GPS navigací, plánování pohybů robota, až po třeba rozhodovací systémy. Petr Hliněný, Fl MU Brno, 2014 14/24 Fl: IB000: Procházení grafu Dijkstrův algoritmus Algoritmus 8.11. Hledání nejkratší cesty mezi u a v v kladně váž. grafu. • Vstup: Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus váhy w hran. Počáteční vrchol u a koncový v, • Úschovna U <— {(u, d(u) = 0)}. • Dokud ř7 ^ 0, opakujeme: * Zvolíme (x, d(x)) G U takové, že d(x) je minimální. Odebereme U <— U \ {(x, d(x))} a zafixujeme hodnotu d(x). c * Pokud x = v, algoritmus může skončit, c * Pro všechny hrany / G E (G) vycházející z x provedeme: - Nechť y je druhý konec hrany / = xy; a nechť ď(y) = d(x) + w(f) (nová cesta do y přes x). - Pokud (y, d(y)) 0 U, nebo (y, d(y)) G U pro d{y) > ď(y), odložíme U 00 1 i* oc \ 2 \ 0 / ®-----4r u i oc Petr Hliněný, Fl MU Brno, 2014 16/24 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2014 17/24 Fl: IB000: Procházení grafu Důkaz správnosti Věta 8.13. Dijkstrův Algoritmus 8.11 pro kladně vážený graf (G,w) vždy správně najde nejkratší cestu mezi danými vrcholy u,v. c Důkaz vede přes následující zesílené tvrzení indukcí: • V každé iteraci Algoritmu 8.11 hodnota d(x) udává nejkratší vzdálenost z vrcholu u do x při cestě pouze po už zpracovaných vnitřních vrcholech. V bázi indukce dovolujeme pouze cesty používající u a x, tj. jen hrany vycházející z u. Ty jsou v první iteraci algoritmu probrány a jejich délky uloženy do U. c V každém dalším kroku je vybrán jako vrchol x ke zpracování ten, který má ze všech nezpracovaných vrcholů nejkratší nalezenou vzdálenost od počátku u. V tom okamžiku je d(x) platnou vzdáleností do x, neboť jakákoliv cesta přes jiný nezpracovaný vrchol nemůže být kratší díky nezápornosti vah w. Z toho pak vyplývá, že zpracování vrcholu x správně upraví dočasné vzdálenosti odložené do U. Důkaz indukcí je hotov. □ Petr Hliněný, Fl MU Brno, 2014 18/24 Fl: IB000: Procházení grafu 8.4 Problém minimální kostry V tomto prípade nebudeme hledat nejkratší spojení mezi dvojicí vrcholu, ale mezi všemi vrcholy najednou - této úloze se říká minimální kostra neboli MST („minimum spanning tree"). Petr Hliněný, Fl MU Brno, 2014 19/24 Fl: IB000: Procházení grain V návaznosti na Oddíl 7.4 definujeme toto: Definice: Podgraf T Q G souvislého grafu G se nazývá kostrou, pokud * T je stromem a * V(T) = V(G), neboli T propojuje všechny vrcholy G. c Váhou (délkou) kostry T C G váženého souvislého grafu (G,w) rozumíme Definice 8.14. Problém minimální kostry (MST) ve váž. grafu (G,w) hledá kostru T C G s nejmenší možnou vahou (přes všechny kostry grafu G)x Problém minimálni kostry je ve skutečnosti historicky úzce svázán s jižní Moravou a Brnem, konkrétně s elektrifikací jihomoravských vesnic ve dvacátých letech! Právě na základě tohoto praktického optimalizačního problému brněnský matematik Otakar Borůvka jako první podal řešení problému minimální kostry v roce 1926. Petr Hliněný, Fl MU Brno, 2014 20/24 Fl: IB000: Procházení grafu Hladové řešení minimální kostry 3 4 3 \ 3 1 l\ Á 1 4 2 3 4 3 3 > 1 \ / 1 4 2 Metoda 8.15. Hladový postup pro minimální kostru grafu (G,w). Mějme dán souvislý vážený graf G s ohodnocením hran w. • Seřadíme všechny hrany G jako E(G) = (ei, e2,..., em) tak, že w{e{) < w(e2) < ■■ < w{em). c • Inicializujeme prázdnou kostru T = (V(G),0). • Po řadě pro i = 1, 2,... , m provedeme následující: * Pokud T + e,t nevytváří kružnici, tak E(T) <- E(T) U {e,t}. (Neboli pokud e,i spojuje různé komponenty souvislosti dosavadního lib) • Na konci T obsahuje minimální kostru grafu G. Ukážeme si postup hladového algoritmu pro vyhledání kostry výše zakresleného grafu. Hrany si nejprve seřadíme podle jejich vah 1,1,1,1,2,2,2,2,3,3,3,4,4. V obrázku průběhu algoritmu používáme tlusté čáry pro vybrané hrany kostry a tečkované čáry pro zahozené hrany. Hrany teď postupně přidáváme do kostry / zahazujeme. .. Získáme tak minimální kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2= 12, která je v tomto případě (náhodou) cestou, na posledním obrázku vpravo. Petr Hliněný, Fl MU Brno, 2014 22/24 Fl: IB000: Procházení grafu Jarníkův (Primův) algoritmus Algoritmus 8.16. Hledání minimální kostry ve váž. grafu (G,w). Níže uvedená specifická implementace procházení grafu využívá úschovnu rozšířeným způsobem, kdy ukládá i příchozí hranu do vrcholu. • Vstup: Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus váhy w hranu • Vybereme lib. počátek prohledáváním G V (G); úschovna U <— {(u, 0)}. Kostra T = (F(G),0). • Dokud Č7 7^ 0, opakujeme: * Zvolíme (x, e) G U takové, že w(e) je minimální (kde io(0) = 0). Odebereme U <—U \ {(x, e)}. * Přidáme E (T) ^— E (T) U {e} (nová hrana do budoucí kostry), c * Pro všechny hrany / G E (G) vycházející z x provedeme: - Nechť y je druhý konec hrany / = xy. - Pokud (y, f) 0 U, nebo (y, f) G U pro nějaké w(f') > w(f), odložíme U