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, 2012 1/20 Fl: IB000: Procházení grafu 8.1 Jak obecně projít souvislý graf Pro vytvoření co nejobecnějšího schématu algoritmu pro procházení grafem vystačíme s následujícími datovými stavy a pomocnou strukturou: • 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 • 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 provádějí konkrétní programové akce pro prohledání a zpracování našeho grafu. Petr Hliněný, Fl MU Brno, 2012 2/20 Fl: IB000: Procházení grafu Algoritmus 8.1. 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 lib. v G U; odebereme U -í— U\{v}. (!) * Pokud sta v (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, 2012 3/20 Fl: IB000: Procházení grafu Některé implementace procházení grafu Jak je vlastně proveden krok (!); „zvolíme lib. 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 Dále zmíníme i 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 vzá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, 2012 4/20 Fl: IB000: Procházení grafu * Konkrétní ukázky BFS a DFS Příklad 8.2. 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, 2012 5/20 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2012 6/20 Fl: IB000: Procházení grafu Příklad 8.3. Ukázka průchodu předchozím grafem do hloubky z vrcholu a. Petr Hliněný, Fl MU Brno, 2012 7/20 Fl: IB000: Procházení grafu 8.2 Vzdálenost v grafu Definice 8.4. 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. Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) = dc(v,u). Lema 8.5. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: yu,v,wEV(G) : dc(u,v) + dciv^w) > dc(u,w). Petr Hliněný, Fl MU Brno, 2012 8/20 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.6. 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 V důkaze postupujeme indukcí podle vzdálenosti dc(u,v). .. □ Petr Hliněný, Fl MU Brno, 2012 9/20 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.7. (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 Lema 8.8. 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, 2012 10/20 Fl: IB000: Procházení grafu Příklad 8.9. 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, 2012 11/20 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, 2012 12/20 Fl: IB000: Procházení grafu Dijkstrův algoritmus Algoritmus 8.10. 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 ď(y), odložíme U^{U\ (y, d(y))) U {(y, ď (y))} (nová, lepší dočasná vzdálenost do y), c • Výstup: d(v) udává váženou vzdálenost z u do v. Petr Hliněný, Fl MU Brno, 2012 13/20 Fl: IB000: Procházení grafu Klíčem k pochopení činnosti Dijkstrova algoritmu je „uvidět", že v každé jeho fázi jsou správně nalezeny všechny nejkratší cesty z u vedoucí po zpracovaných vrcholech. Postupem prohledávání grafu se tak jednou dostaneme až k určení správné vzdálenosti cíle v. c Příklad 8.11. Ukázka běhu Dijkstrova Algoritmu 8.10 pro nalezení nejkratší cesty mezi vrcholy u, v v následujícím váženém grafu. oc v / \ 2 oo f. 1 OO i( oc ' \ / 9 ' r \ / * / ^ 3 \ / \ / 2 \ 0 / ®------V u i oc > 00 1 i* oc v /' 2 Petr Hliněný, Fl MU Brno, 2012 14/20 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2012 15/20 Fl: IB000: Procházení grafu Důkaz správnosti Věta 8.12. Dijkstrův Algoritmus 8.10 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.10 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, 2012 16/20 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, 2012 17/20 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.13. 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 1928. Petr Hliněný, Fl MU Brno, 2012 18/20 Fl: IB000: Procházení grafu Hladové řešení minimální kostry Metoda 8.14. 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 {ej. (Neboli pokud e^ spojuje různé komponenty souvislosti dosavadního lib) • Na konci T obsahuje minimální kostru grafu G. Věta 8.15. Hladový postup korektně spočítá minimální kostru grafu (G, w). c Důkaz (náznak): Pro spor předpokládejme, že T\ je kostra spočítaná Metodou 8.14 a T2 nějaká minimální kostra „blízká" Tlt kde ď£(T2) < d^{T{). Nyní najdeme jinou min. kostru T3 „bližší" Ti, což je spor s volbou T2. □ Petr Hliněný, Fl MU Brno, 2012 19/20 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 • Úschovna U <- {(u, 0)}. Kostra T = (V(G), 0). • Dokud ř7 ^ 0, opakujeme: * Zvolíme (x, e) G U takové, že w(e) je minimální (kde io(0) = 0). Odebereme U «;(/), odložíme U<-(U\{{y,f')})u{{y,f)} • Výstup: T udává výslednou minimální kostru. Petr Hliněný, Fl MU Brno, 2012 20/20 Fl: IB000: Procházení grafu