8 Procházení a zpracování grafů 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í a jednoduchého zpracování grafu. * Nejkratší cesta v grafu a Dijkstrův algoritmus. * Minimální kostra grafu a její základní algoritmy. Petr Hliněný, Fl MU Brno, 2016 1/22 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á jeden ze stavů ... t * počáteční (iniciační) - ten 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, volitelně spolu s dodatečnou specifickou informací. • 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 zpracování našeho grafu. Petr Hliněný, Fl MU Brno, 2016 2/22 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í. • Vybereme lib. počátek prohledávání u G V(G)\ úschovna U <— {u}. □ • Dokud U ^ 0, opakujeme: * Zvolíme libovolně v G U; odebereme U <— U \ {v}. (!)c * Pokud stav(v) = zpracovaný, vracíme se na start cyklu. (*) * Případně provedeme libovolnou akci ZPRACUJ(v). * Pro všechny hrany / G E (G) vycházející z v provedeme: - Nechť w je druhý konec hrany / = vw\ - pokud stav(w) ^zpracovaný, odložíme U <— U U {w}. (**)□ * stav(i?) zpracovaný; na start cyklu. • Souvislá komponenta G určená v je celá prohledaná a zpracovaná. Všimněte si, že v bodě (**) obecně může docházet k násobnému ukládání, což v prakt. implementaci často obejdeme pouhou změnou stavu vrcholu v U. Petr Hliněný, Fl MU Brno, 2016 3/22 Fl: IB000: Procházení grafu Konkrétní ukázka jednoduchého prohledání Příklad 8.3. Ukázka průchodu následujícím grafem z vrcholu a do šírky, tj. podle Algoritmu 8.2 s implementací úschovny jako fronty vrcholů („first in, first out"). a ® 9 f u ' L • * b h +-----fc i \\ i i \ / \ i 1 \ 1 \ J„ — * C N / / j \ \ \ \ \ \ ^ \ -± e Petr Hliněný, Fl MU Brno, 2016 4/22 Fl: IB000: Procházení grafu Značení v prohledávaném grafu: barevně aktuálně zpracovávaný vrchol a jeho hrany objevující nové vrcholy, kroužkem a plnou čarou již zpracované vrcholy a hrany. Petr Hliněný, Fl MU Brno, 2016 5/22 Fl: IB000: Procházení grafu Některé varianty procházení grafu Jak je vlastně proveden krok (!); „Zvolíme libovolně v G Č7"? Právě tato volba zásadně předurčuje výslednou podobu procházení grafu G a okruh odpovědí, které je schopen algoritmus vypočítat. V našem textu se blíže zabýváme pouze následujícími jednoduchými variantami: • Procházení „do šířky", známé pod zkratkou BFS - úschovna ř/ je implementovaná jako fronta, neboli je voleno v G U od prvních vrcholů vložených do U. nCasto se používá v situacích, kdy konkrétní pořadí volby v G U není důležité, jako například při vypsání souvislých komponent grafu. • Dijkstrův algoritmus pro nej kratší cesty v grafu - z úschovny vybíráme vždy vrchol nejbližší (dosud určenou celkovou vzdáleností) k počátečnímu u. • Jarníkův algoritmus pro minimální „propojení" grafu (jeho kostru) -z úschovny vybíráme vždy vrchol nejbližší k již zpracované části grafu. Poznámka: Jarníkův algoritmus se ve světové literatuře se obvykle připisuje Američanu Primoví, který jej však objevil a publikoval až skoro 30 let po Jarníkovi. Petr Hliněný, Fl MU Brno, 2016 6/22 Fl: IB000: Procházení grafu Procházení do šířky a do hloubky Pro jen letmou ukázku výrazně odlišného způsobu procházení grafu se podíváme na základní procházení do hloubky (známé pod zkratkou DFS). Zjednodušeně řečeno, DFS získáme, pokud v Algoritmu 8.2 implementujeme úschovnu U jako zásobník, avšak musíme korektně zpracovat násobné ukládání téhož vrcholu (posune k vrcholu zásobníku). Rozdíl mezi BFS a DFS pak jednoduše ilustrují tyto obrázky tzv. stromů procházení (sestávají z hran, kterými byly objeveny nové vrcholy grafu): BFS DFS Petr Hliněný, Fl MU Brno, 2016 7/22 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 nejkratší cesty mezi u a v v G. Pokud cesta mezi u,v neexistuje, je vzdálenost definována dc{u,v) — oo. Neformálně řečeno, vzdálenost mezi u, v je rovna nej menším u počtu hran, které musíme překonat, pokud se chceme dostat z u do v. Speciálně vždy platí dc(u,u) = 0. 1-•-—) i-. č—-•- Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc{u^v) — dciy^u). Lema 8.5. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: Mu, v, w G V(G) : dc{u, v) + dc{v, w) > dc{u, w). Petr Hliněný, Fl MU Brno, 2016 8/22 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 šírky. Věta 8.6. Algoritmus procházení grafu do šířky lze přímo použít pro výpočet grafové vzdálenosti z daného vrcholu u. • 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. 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) < (Ig{u,w). Pak při algoritmu procházení grafu G do šírky z vrcholu u je vrchol v nalezen dříve než vrchol w. V důkaze postupujeme indukcí podle vzdálenosti dc{u^v). .. □ Petr Hliněný, Fl MU Brno, 2016 9/22 Fl: IB000: Procházení grafu 8,3 Hledání nej kratší 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. Definice 8.7. (vážená vzdálenost) Mějme (kladně) vážený graf (G,w). Váženou délkou cesty P je d%(P) = V w(é). Váženou vzdáleností y (G,w) mezi dvěma vrcholy u,v pak je ďc{u, v) — min{cř^(P) : P je cesta s konci u, v} .□ 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, 2016 10/22 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.) Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi 6, c. Co ale mezi a,6?^ Je jejich vzdálenost 6?n 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 šírky není korektní pro hledání vzdáleností ve váženém grafu. □ Petr Hliněný, Fl MU Brno, 2016 11/22 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. ř Univerzita obranV - i: Petr Hliněný, Fl MU Brno, 2016 12/22 Fl: IB000: Procházení grafu Dijkstrův algoritmus Algoritmus 8.10. Hledání nejkratší cesty mezi u a v y 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ý vl • Úschovna U {(?/, d(u) = 0)}. □ • Dokud U ^ 0, opakujeme: * Zvolíme (x, d{x)) G U takové, že d(x) je minimální. Odebereme U <— Č7 \ {(x, □ * Pokud x = v, algoritmus může skončit. * 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 [/, nebo (y, d(y)) G U pro d(y) > ď(y), odložíme U^ \ / \ / ^ \ \ / 2 \ 5/\ / oc K / \ 2 \ 0 ^ \ '' 2 ----- > oc ®--- i/ 1 oc Petr Hliněný, Fl MU Brno, 2016 14/22 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2016 15/22 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 nej kratší cestu mezi danými vrcholy u, v. 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í ua 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. 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, 2016 16/22 Fl: IB000: Procházení grafu 8.4 Problém minimální kostry V tomto případě nebudeme hledat nejkratší spojení mezi dvojicí vrcholů, 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, 2016 17/22 Fl: IB000: Procházení grafu ■r V návaznosti na Oddíl 7.4 definujeme toto: Definice: Podgraf T C 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. □ 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).ľ 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, 2016 18/22 Fl: IB000: Procházení grafu Hladové řešení minimální kostry 3 4 3 3 4 3 14 2 14 2 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, • • •, em) tak, že w[e{) < w(e2) < • • • < w(em). □ • Inicializujeme prázdnou kostru T — (F(G),0). • Po řadě pro i — 1, 2,... , m provedeme následující: * Pokud T + a nevytváří kružnici, tak E(T) w(f), odložíme (U\ {(y, /')}) U {(y, /)}. □ • Výstup: T udává výslednou minimální kostru. Petr Hliněný, Fl MU Brno, 2016 21/22 Fl: IB000: Procházení grafu Petr Hliněný, Fl MU Brno, 2016 22/22 Fl: IB000: Procházení grafu