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, 2015 1/23 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 • 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, 2015 2/23 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, 2015 3/23 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 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 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, 2015 4/23 Fl: IB000: Procházení grafu Ilustrace rozdílu mezi BFS a DFS Příklad 8.3. Pro lepší pochopení rozdílného průběhu při prohledávání grafu do šířky a do hloubky uvádíme následující dva jednoduché obrázky. Zobrazeny jsou „cestičky" (přesněji hrany), kterými byly objeveny nové vrcholy grafu: BFS DFS Z Petr Hliněný, Fl MU Brno, 2015 5/23 Fl: IB000: Procházení grafu ^Konkrétní ukázky BFS a DFS Příklad 8.4. Ukázka průchodu následujícím grafem do šířky z vrcholu a. f -----* e ' ~~ ! N ' i ^ s ft---------4 j » d liU i ' \ Jí-* c a ®------4r b Petr Hliněný, Fl MU Brno, 2015 6/23 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2015 7/23 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2015 8/23 Fl: IB000: Procházení grafu 8.2 Vzdálenost v grafu Definice 8.6. 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ě vždy platí do(u,u) = 0. Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) = dc(v,u). Lema 8.7. 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, 2015 9/23 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.8. 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, 2015 10/23 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.9. (vážená vzdálenost) Mějme (kladně) vážený graf (G,w). Váženou délkou cesty P je dg(P) = V 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.10. 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, 2015 11/23 Fl: IB000: Procházení grafu Příklad 8.11. 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, 2015 12/23 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, 2015 13/23 Fl: IB000: Procházení grafu Dijkstrův algoritmus Algoritmus 8.12. 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 00 1 i* oc 2 \ 0 / ® — u i x / 2 OC Petr Hliněný, Fl MU Brno, 2015 15/23 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2015 16/23 Fl: IB000: Procházení grafu Důkaz správnosti Věta 8.14. Dijkstrův Algoritmus 8.12 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.12 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, 2015 17/23 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, 2015 18/23 Fl: IB000: Procházení grafu r 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.15. 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, 2015 19/23 Fl: IB000: Procházení grafu Hladové řešení minimální kostry 3 4 3 3 4 3 14 2 14 2 Metoda 8.16. 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, 2015 21/23 Fl: IB000: Procházení grafu Jarníkův (Primův) algoritmus Algoritmus 8.17. 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í u G V (G). Úschovna U ^ {(u, 0)} a počáteční kostra T ^— (V(G),$). c • 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 / = xy a /' je takové, že (y, /') G U. - Pokud takové /' neexistuje nebo w(f) > w(f), odložíme U