Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Základy matematiky a statistiky pro humanitní obory II Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 3 Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Obsah přednášky 1 Další pojmy z teorie grafů 2 Algoritmy procházení grafu 3 Kruskalův algoritmus 4 Dijkstrův algoritmus Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Souvislé komponenty Souvislé komponenty Souvislé komponenty největší souvislé podgrafy → mezi každými dvěma vrcholy existuje cesta Silně souvislé komponenty v případě orientovaných grafů mezi každými dvěma vrcholy existuje cesta tam i zpět Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Vzdálenost v grafu Vzdálenost v grafu Délka cesty neohodnocený graf: počet hran v cestě ohodnocený graf: součet ohodnocení jednotlivých hran v cestě Vzdálenost mezi dvěma vrcholy X a Y je délka nejkratší cesty z X do Y Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Kořen a listy stromu Kořen a listy stromu Kořen stromu jeden vyznačený vrchol kreslíme většinou nahoře :) Listy stromu vrcholy stupně 1, které nejsou kořenem kreslíme většinou dole Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Kořen a listy stromu Příklad – syntaktický strom I saw a man with a telescope . Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Kostra grafu Kostra grafu Podgraf, který obsahuje všechny vrcholy původního grafu je strom → musíme odstranit všechny cykly Minimální kostra grafu pro ohodnocený graf kostra s nejmenším součtem ohodnocení hran analogicky maximální kostra Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Procházení grafu Procházení grafu Např. hledáme určitý vrchol, chceme projít všechny, ... Procházení do hloubky – depth-first search začínáme z nějakého vrcholu, ten označíme označíme libovolný sousední neoznačený vrchol a pokračujeme z něj pokud to dál nejde (všechny sousední vrcholy jsou označené), vrátíme se k nejbližšímu vrcholu, ze kterého to ještě jde Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Procházení grafu Procházení grafu Procházení do šířky – breadth-first search začínáme z nějakého vrcholu, ten označíme vybereme všechny sousední neoznačené vrcholy a přidáme je do seznamu postupně ze začátku seznamu odebíráme a provádíme předchozí kroky končíme, když je seznam prázdný Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Procházení grafu Procházení do hloubky z vrcholu u DFS(G, u) ============ označ u for všechny hrany (u, v) vycházející z vrcholu u: if v není označen: DFS(G, v) Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Procházení grafu Procházení do šířky z vrcholu u BFS(G, u) ============ Q = [u] while Q je neprázdný: odstraň první prvek z Q a přiřaď jej do t označ t přidej všechny neoznačené sousedy t na konec Q Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Kruskalův algoritmus Kruskalův algoritmus Vstup neorientovaný graf G ohodnocení hran w Výstup minimální kostra grafu G Algoritmus je tzv. hladový v každém kroku vybírá lokálně optimální možnost Idea setřídit hrany podle ohodnocení v každém kroku přidat do kostry tu nejmenší, která nevytvoří cyklus udržujeme si seznam souvislých komponent kostry Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Kruskalův algoritmus Kruskalův algoritmus (G, w) K ← [ ]; comp ← {} for u in G(V ): comp[u] ← set(u) setřiď G(E) podle w for (u, v) in G(E): if comp[u] = comp[v] : K.append((u, v)) newset = union(comp[u], comp[v]) for x in newset : comp[x] ← newset K je minimální kostra grafu Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus Vstup graf s hranami ohodnocenými funkcí w ohodnocení hran musí být nezáporné počáteční vrchol s Výstup vzdálenosti z vrcholu s do všech dalších vrcholů grafu Idea udržujeme si nejmenší známé vzdálenosti do všech vrcholů na začátku nekonečno procházíme postupně vrcholy a hodnoty upravujeme Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus (G, s) for u in G(V ): d[u] ← infinity d[s] ← 0 N ← G(V ) p ← {} while N = [ ]: u ← vrchol z N s nejmenší hodnotou d[u] for všechny hrany (u, x) vycházející z vrcholu u: alt ← d[u] + w((u, x)) if alt < d(x) : d[x] ← alt; p[x] ← u odstraň u z N d jsou vzdálenosti vrcholů z vrcholu s p obsahuje předchozí vrcholy na nejkratší cestě z s Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory II