Grafy Procházení grafu Složitější algoritmy Shrnutí Grafové algoritmy Grafy Procházení grafu Složitější algoritmy Shrnutí Obsah 1 Grafy Pojem grafu Příklady grafů Reprezentace grafu 2 Procházení grafu Procházení do šířky Procházení do hloubky Aplikace Příklady 3 Složitější algoritmy Nejkratší vzdálenosti Kostra grafu Další 4 Shrnutí Grafy Procházení grafu Složitější algoritmy Shrnutí Motivační příklad I Kde prokopat zeď, aby se bludiště stalo průchodným? Grafy Procházení grafu Složitější algoritmy Shrnutí Motivační příklad II šedé pole = žebřík o patro nahoru Grafy Procházení grafu Složitější algoritmy Shrnutí Motivační příklad I řešení Grafy Procházení grafu Složitější algoritmy Shrnutí Motivační příklad II řešení Grafy Procházení grafu Složitější algoritmy Shrnutí Pojem grafu Graf Základní pojmy: uzly (vrcholy) hrany: orientované, neorientované, vážené stupeň vrcholu cesta v grafu, dosažitelnost, cyklus souvislost, komponenty strom, klika (úplný graf) Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady grafů Použití grafů dopravní sítě (silniční, vlaková, letecká, ...) elektrická síť Internet sociální sítě plánování: závislosti mezi úlohami stavový prostor logické úlohy Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady grafů Potravní řetězce uzly: zvířata, hrany: pokud jedno žere druhé Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady grafů Teroristi Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady grafů Co je to? Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady grafů Logická úloha: Misionáři a kanibalové 3 misionáři, 3 kanibalové řeka, 1 loďka (max 2 lidé) víc kanibalů jak misionářů na jednom místě problém (jen jeden misionář a jeden kanibal umí pádlovat) zkuste: najít řešení ,,najít v tom graf Grafy Procházení grafu Složitější algoritmy Shrnutí Reprezentace grafu Reprezentace grafu v počítači seznamy sousedů pro každý vrchol seznam jeho sousedů vhodné pro řídké matice matice souslednosti binární matice pro každou dvojici vrcholů: sousedí (1) / nesousedí (0) vhodné pro malé nebo husté matice Grafy Procházení grafu Složitější algoritmy Shrnutí Reprezentace grafu Reprezentace grafu: příklad neorientovaný graf Grafy Procházení grafu Složitější algoritmy Shrnutí Reprezentace grafu Reprezentace grafu: příklad orientovaný graf Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení grafu procházení grafu = základní operace nad grafy procházení do šířky procházení do hloubky Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do šířky Procházení do šířky BFS = breadth-first search ,,povodeň z počátečního vrcholu realizace pomocí fronty pro aktuální vrchol: projdu všechny sousedy pokud soused nebyl navštíven, dám jej do fronty Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do šířky Ilustrace Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do šířky Ilustrace 2 Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do šířky Pseudokód Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do šířky Procházení do šířky ­ poznámky procházím v pořadí podle vzdálenosti od zdroje jednoduché napočítat vzdálenosti (počet kroků) strom předchůdců ­ rekonstrukce nejkratších cest Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do hloubky Procházení do hloubky DFS = depht-first search ,,zavrtávání se do hloubky realizace pomocí rekurze (zásobníku) pokud najdu nenavštíveného souseda, začnu prohledávat z něho ostatní sousedy obsloužím až později Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do hloubky Ilustrace Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do hloubky Ilustrace 2 Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do hloubky Pseudokód Grafy Procházení grafu Složitější algoritmy Shrnutí Procházení do hloubky Procházení do hloubky ­ poznámky jednoduché na implementaci pomocí rekurze užitečné vlastnosti využitelné pro aplikace, např. detekce cyklů (silné) komponenty souvislosti topologické třídění Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Aplikace prohladávání komponenty spojitosti hledání nejkratších cest detekce cyklů bipartita Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Komponenty souvislosti komponenta souvislosti = maximální množina vrcholů U V , každé dva vrcholy z U vzájemně dosažitelné detekce pomocí prohledávání (do šířky, do hloubky) Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Hledání nejkratších cest pokud všechny hrany mají váhu 1 hledání nejkratších cest pomocí BFS jednoduchá úprava Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Detekce cyklu cyklus (kružnice) ­ cesta z vrcholu sama do sebe jak poznat, zda graf obsahuje cyklus? Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Detekce cyklu cyklus (kružnice) ­ cesta z vrcholu sama do sebe jak poznat, zda graf obsahuje cyklus? neorientovaný ­ spočítat počet hran a vrcholů orientovaný ­ pomocí DFS kontrola, zda je soused aktuálního vrcholu na zásobníku Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Bipartitní graf bipartitní graf existuje rozdělení množiny vrcholů na V1, V2 hrany vedou pouze mezi V1 a V2, nikoliv v rámci množin jak poznat, zda je graf bipartitní? Grafy Procházení grafu Složitější algoritmy Shrnutí Aplikace Bipartitní graf bipartitní graf existuje rozdělení množiny vrcholů na V1, V2 hrany vedou pouze mezi V1 a V2, nikoliv v rámci množin jak poznat, zda je graf bipartitní? pomocí BFS (či DFS) ­ průběžně přiřazuji do množiny 1/2 a kontroluji Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady Použití procházení grafu mnoho problémů lze řešit jednoduše pomocí aplikace procházení grafu klíčové správně ,,pojmenovat graf Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady Příklad: robot v bludišti čtverečkované bludiště robot s operacemi: krok, rotace vlevo, rotace vpravo jak se dostat na co nejmíně operací z jednoho místa do druhého Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady Logická úloha: Misionáři a kanibalové 3 misionáři, 3 kanibalové řeka, 1 loďka (max 2 lidé) víc kanibalů jak misionářů na jednom místě problém (jen jeden misionář a jeden kanibal umí pádlovat) zkuste: najít řešení ,,najít v tom graf Grafy Procházení grafu Složitější algoritmy Shrnutí Příklady Příklad: generování bludiště bludiště graf generování bludiště pomocí randomizovaného DFS prokopávání zdí Grafy Procházení grafu Složitější algoritmy Shrnutí Složitější algoritmy nad grafy nejkratší vzdálenosti kostra grafu eulerovská cesta ­ domečkologie hamiltonovská cesta ­ problém obchodního cestujícího toky v sítích Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti Nejkratší vzdálenosti více různých problémů váhy hran: konstantní (1) přirozená čísla celá čísla odkud kam: z jednoho vrcholu do druhého (SSSP = single source shortest path) mezi všemi dvojicemi vrcholů (APSP = all pairs shortest path) Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti Dijkstrův algoritmus SSSP s kladnými hranami Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti Dijkstrův algoritmus SSSP s kladnými hranami opakuj: 1 vyber nezpracovaný vrchol s nejmenší vzdáleností od startu 2 zpracuj vrchol: aktualizuj vzdálenost sousedů efektivní implementace: prioritní fronta Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti APSP s kladnými hranami naivně: spustit SSSP z každého vrcholu neefektivní Floyd-Warshalův algoritmus: nejkratší vzdálenosti vedoucí přes vrchol 1 nejkratší vzdálenosti vedoucí přes vrcholy 1, 2 nejkratší vzdálenosti vedoucí přes vrcholy 1, 2, 3 ... Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti Floyd-Warshalův algoritmus APSP s kladnými hranami Grafy Procházení grafu Složitější algoritmy Shrnutí Nejkratší vzdálenosti Celočíselné hrany mohou být i záporné váhy hran, problémy: nelze jednoduše najít ideální pořadí počítání vzdáleností záporný cyklus obecný přístup: opakovaná ,,relaxace hran detekce záporných cyklů Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kostra grafu kostra grafu = minimální množina hran, tak že graf je spojitý ceny hran nejlevnější kostra grafu aplikace: např. elektrická síť historie: prof. Borůvka Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kruskalův algoritmus setřídit hrany podle ceny postupně procházet hrany: vytvoří hrana cyklus? ano zahodit ne použít datová struktura: union-find Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kruskalův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kruskalův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kruskalův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Kruskalův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Primův algoritmus začít od nejlevnější hrany postupně ,,přilepujeme další sousedící hrany datová struktura: prioritní fronta Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Primův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Primův algoritmus Grafy Procházení grafu Složitější algoritmy Shrnutí Kostra grafu Nečekaná aplikace: generování bludiště další způsob jak generovat bludiště budujeme ,,kostru ­ bouráme zdi Kruskal, Prim ­ každý trochu jiná bludiště Grafy Procházení grafu Složitější algoritmy Shrnutí Další Toky v sítích tok v síti: např. voda, elektřina, energie (potravní řetězec) uzly: zdroj, dřez hrany: maximální kapacita podmínky: zachování kapacity konzistence uzlů: co přiteče, to odteče problém: hledání maximálního toku řešení: postupné ,,fecování toku Grafy Procházení grafu Složitější algoritmy Shrnutí Další Eulerovský cyklus eulerovský cyklus = navštívit všechny hrany právě jednou problém 1: existuje eulerovský cyklus? problém 2: vypsat cyklus oboje jednoduše řešitelné Grafy Procházení grafu Složitější algoritmy Shrnutí Další Hamiltonovský cyklus hamiltonovský cyklus = navštívit všechny uzly právě jednou problém obchodního cestujícího ­ vážené hrany obtížné (NP-úplné), hrubá síla, heuristiky Grafy Procházení grafu Složitější algoritmy Shrnutí Shrnutí graf, reprezentace prohledávání do hloubky, do šířky aplikace prohledávání složitější algoritmy: cesty, kostry, toky, cykly, ...