Grafové algoritmy IB111 Programování a algoritmizace 2011 Motivační příklad I Kde prokopat zeď, aby se bludiště stalo průchodným? Motivační příklad II šedé pole = žebřík o patro nahoru Motivační příklad III Lze obrázek nakreslit jedním (uzavřeným) tahem? Motivační příklad I řešení Motivační příklad II řešení Motivační příklad III Lze obrázek nakreslit jedním (uzavřeným) tahem? spočítat počty sousedů (stupeň vrcholu) řešitelné – maximálně dva stupně liché uzavřený tah – všechny stupně sudé 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) 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 Potravní řetězce uzly: zvířata, hrany: pokud jedno žere druhé Teroristi Co je to? 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 Reprezentace grafu v počítači seznamy sousedů pro každý vrchol seznam jeho sousedů vhodné pro řídké matice matice sousednosti binární matice pro každou dvojici vrcholů: sousedí (1) / nesousedí (0) vhodné pro malé nebo husté matice Reprezentace grafu: příklad neorientovaný graf Reprezentace grafu: příklad orientovaný graf Procházení grafu procházení grafu = základní operace nad grafy procházení do šířky procházení do hloubky 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 Ilustrace Ilustrace 2 Pseudokód 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 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 Ilustrace Ilustrace 2 Pseudokód 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í Aplikace prohledávání komponenty souvislosti hledání nejkratších cest detekce cyklů bipartita 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) Hledání nejkratších cest pokud všechny hrany mají váhu 1 hledání nejkratších cest pomocí BFS jednoduchá úprava Detekce cyklu cyklus (kružnice) – cesta z vrcholu sama do sebe jak poznat, zda graf obsahuje cyklus? Detekce cyklu cyklus (kružnice) – cesta z vrcholu sama do sebe jak poznat, zda graf obsahuje cyklus? neorientovaný, souvislý – spočítat počet hran a vrcholů orientovaný – pomocí DFS kontrola, zda je soused aktuálního vrcholu na zásobníku 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í? 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 Použití procházení grafu mnoho problémů lze řešit jednoduše pomocí aplikace procházení grafu klíčové správně „pojmenovat graf Příklad: bludiště základní 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 Příklad: tři body v bludišti cíl: najít nejkratší spojnici tří bodů Příklad: bludištěm s dynamitem 1 co nejméně použití dynamitu 2 co nejkratší cesta Příklad: číselné bludiště 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 Příklad: generování bludiště bludiště ∼ graf generování bludiště pomocí randomizovaného DFS – prokopávání zdí 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 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) Dijkstrův algoritmus SSSP s kladnými hranami 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 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 ... Floyd-Warshalův algoritmus APSP s kladnými hranami 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ů Kostra grafu kostra grafu = minimální množina hran, tak že graf je souvislý ceny hran → nejlevnější kostra grafu aplikace: např. elektrická síť historie: prof. Borůvka Kruskalův algoritmus setřídit hrany podle ceny postupně procházet hrany: vytvoří hrana cyklus? ano → zahodit ne → použít datová struktura: union-find Kruskalův algoritmus Kruskalův algoritmus Kruskalův algoritmus Kruskalův algoritmus Primův algoritmus začít od nejlevnější hrany postupně „přilepujeme další sousedící hrany datová struktura: prioritní fronta Primův algoritmus Primův algoritmus 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ě 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 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é 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 Shrnutí graf, reprezentace prohledávání do hloubky, do šířky aplikace prohledávání složitější algoritmy: cesty, kostry, toky, cykly, ...