1 Algorytmy i Struktury Danych GrafyWykład 6 Prowadzący: dr Paweł Drozda
2 Plan wykładu Podstawowe pojęcia grafowe Reprezentacja grafówProblemy grafowe Algorytmy Przeszukiwanie w głąb i wszerz Minimalnie drzewo rozpinające Najkrótsze ścieżki Inne dr Paweł Drozda
3 Pojęcie grafu (nieskierowany)Nieformalnie: zbiór wierzchołków oraz krawędzi łączących te wierzchołki Formalnie: Grafem (nieskierowanym) nazywamy parę G=(V,E) V – zbiór wierzchołków E – zbiór krawędzi, e1 v4 e2 v3 v1 e3={v2,v3} e4 v2 dr Paweł Drozda
4 Graf skierowany Grafem skierowanym nazywamy parę G=(V,A) V – zbiór wierzchołków A – zbiór krawędzi skierowanych (uporządkowanych par różnych wierzchołków) e1 v4 e2 v3 v1 e5 e3=(v3,v2) e4 v2 dr Paweł Drozda
5 Cechy grafu Wierzchołek v i krawędź e są incydentne gdyWierzchołki u i v są sąsiednie gdy G’ jest podgrafem G w.t.w. Stopień wierzchołka deg(v) = liczba krawędzi incydentnych z v dr Paweł Drozda
6 Cechy grafu (2) Graf ważony to trójka G=(V,E,w), gdzie (V,E) jest grafem, a w jest fukcją wag: w:E→R Jeżeli to w(e) jest wagą krawędzi e 7 v4 3 v1 v3 1 5 4 v2 Wagi krawędzi: (v1 ,v3) = 3, (v3 ,v4) = 7, (v4 ,v3) = 1 (v3 ,v2) = 4, (v2 ,v1) = 5 dr Paweł Drozda
7 Cechy grafu(3) Droga to wyznaczona przez krawędzi trasa e1 e2 ei ei+1… pozwalająca na „podróżowanie po grafie” od wierzchołka do wierzchołka Ścieżka to droga nie zawierająca tych samych krawędzi. Ścieżka wyznaczana jest przez wierzchołki ścieżka otwarta: v1v2v3vivi+1… ścieżka zamknięta: v1v2v3vivi+1…v1 Cykl w grafie – droga wracająca do tego samego wierzchołka Graf cykliczny to graf w którym istnieje co najmniej jeden cykl dr Paweł Drozda
8 Spójność grafu Graf jest spójny jeżeli pomiędzy dowolnymi jego wierzchołkami istnieje droga e5 v7 e1 v4 e2 v3 v1 e6 e9 v8 e3 v6 e4 e7 v2 v5 e8 e10 dr Paweł Drozda
9 Reprezentacja grafu Macierz sąsiedztwa – |V|2 elementówLista Sąsiedztwa – lepsza dla grafów rzadkich, t.j. |E|<<|V|2, O(max(V,E))=O(V+E) elementów 1 2 3 4 e1 v4 e2 v3 v1 e3 e4 1: 2→3→null 2: 1→3→null 3: 1→2→4→ null 4: 3→null v2 dr Paweł Drozda
10 Reprezentacja grafu Macierz sąsiedztwa – |V|2 elementówLista Sąsiedztwa – lepsza dla grafów rzadkich, t.j. |E|<<|V|2, O(max(V,E))=O(V+E) elementów 1 2 3 4 5 5 v4 3 v3 v1 1 2 1: (2,2)→(3,3)→null 2: (1,2)→(3,1)→null 3: (1,3)→(2,1)→ (4,5)→ null 4: (3,5)→null v2 dr Paweł Drozda
11 Reprezentacja grafu Dla grafu skierowanego e1 v4 e2 v3 v1 e5 e3 e4 v2e1 v4 e2 v3 v1 e5 e3 e4 v2 1: 1 → 3→null 2: 1→null 3: 2→4→null 4: 3→null dr Paweł Drozda
12 Problem mostów królewieckichCzy można przejść kolejno przez wszystkie mosty tak, żeby każdy przekroczyć tylko raz i wrócić do miejsca, z którego się wyruszyło? Zagadnienie opublikowane przez Eulera w 1736 roku – pierwsza praca n.t. teorii grafów dr Paweł Drozda
13 Algorytmy grafowe Przeszukiwanie grafóww głąb, wszerz Drzewa – szczególna postać grafów Znajdowanie minimalnego drzewa rozpinającego – algorytm Kruskala i Prima Problemy: znajdowanie najkrótszej ścieżki (Dijkstry, Bellmana – Forda, Floyda – Warshalla) znajdowanie ścieżki/cyklu Eulera chińskiego listonosza – najkrótsza droga przechodząca wszystkie krawędzie grafu co najmniej raz znajdowanie ścieżki/cyklu Hamiltona - Θ(n!) komiwojażera – najkrótsza zamknięta ścieżka, przechodząca przez wszystkie wierzchołki (minimalny cykl Hamiltona) kojarzenia małżeństw dr Paweł Drozda
14 Przeszukiwanie wszerzBreadth-First Search dane: graf G(V,E), wierzchołek początkowy s BFS(G,s): zaznacz wszystkie wierzcholki jako nieodwiedzone enqueue(Q,s); zaznacz s jako odwiedzony; while ~empty(Q) do begin w = dequeue(Q); foreach sasiad w do if sasiad nie odwiedzony then begin zaznacz sasiad jako odwiedzony; enqueue(Q, sasiad); end end Zł. czasowa = O(|V|+|E|) Θ(|V|) – inicjalizacja O(|E|) – przeglądanie dr Paweł Drozda
15 Przeszukiwanie w głąb Zł. czasowa = O(|V|+|E|) Θ(|V|) – inicjalizacjaDepth-first search dane: graf G(V,E), wierzchołek początkowy s DFS(G,s): zaznacz wszystkie wierzcholki jako nieodwiedzone push(S,s); zaznacz s jako odwiedzony; while ~empty(S) do begin w = pop(Q); foreach sasiad wierzcholka w do if sasiad nie odwiedzony then begin zaznacz sasiad jako odwiedzony; push(S, sasiad); end end Zł. czasowa = O(|V|+|E|) Θ(|V|) – inicjalizacja O(|E|) – przeglądanie dr Paweł Drozda
16 Minimalne drzewo rozpinająceNiech będzie dany graf G =
17 Przykład minimalne drzewo rozpinająceb f e d c a 1 4 8 2 7 5 10 6 b f e d c a 1 4 8 2 7 5 10 6 Jedno z drzew Minimalne drzewo rozpinające dr Paweł Drozda
18 Algorytm Prima Idea algorytmu Wybieramy dowolnie korzeń szukanego drzewa rozpinającego W każdym kroku algorytmu wybieramy krawędź lekką – tzn. łączącą powstałe do tej pory drzewo z jednym z pozostałych wierzchołków najmniejszym kosztem b f e d c a 1 4 8 2 7 5 10 6 Krawędź lekka (c,d) dr Paweł Drozda
19 Przykład - algorytm Primae f b c 6 3 1 7 5 4 2 10 GRAF a-> b, c b -> a, c, d c -> a, b, d, e, f d -> b, c, e, g e -> c, d, f f -> c, e, g g -> f, d 2 4 5 Start – wierzchołek g: Kolejne wierzchołki: g-f-c-d-e-b-a Kolejne krawędzie: (f, g); (c, f); (c, d); (d,e); (b, c); (a, b) dr Paweł Drozda
20 Kodowanie – algorytm PrimaDla każdego u V k[u] = ∞ p[u]= NIL k[s]=0 Q = V while Q not empty u = EXTRACT–MIN(Q) dla każdego v=sąsiada(u) if v Q i w(u,v) < k[v] then p[v] = u k[v] = w(u,v) dr Paweł Drozda
21 Algorytm Kruskala Jeśli drzewo rozpinające ma mieć koszt minimalny i ma zawierać dany las drzew, to musi też zawierać krawędź e, której koszt jest najmniejszy wśród wszystkich krawędzi nie należących do żadnego z drzew i która łączy dwa wierzchołki z różnych drzew. Utworzyć kolejkę priorytetową PQ z wszystkimi krawędziami grafu, uporządkowanymi ze względu na koszt. Utworzyć początkowy podział Po zbioru V jako rodzinę jednoelementowych zbiorów {x}, gdzie x V (stanowiący las początkowy). Przeglądać kolejno elementy kolejki i jeżeli końce rozważanej krawędzi należą do różnych zbiorów podziału, to krawędź dołączyć do tworzonego drzewa, a zbiory podziału połączyć. dr Paweł Drozda
22 Algorytm Kruskala – przykłade f b c 6 3 1 7 9 4 2 10 Szeregowanie krawędzi (c,d)=1 (d,e)=2 (a,b)=2 (c,f)=3 (b,c)=4 (e,f)=4 (b,d)=6 (a,c)=7 (f,g)=8 (d,g)=9 (c,e)=10 krawędzie wybrane (c,d)=1 (d,e)=2 (a,b)=2 (c,f)=3 (b,c)=4 (e,f)=4 (b,d)=6 (a,c)=7 (f,g)=8 (d,g)=9 (c,e)=10 2 4 8 dr Paweł Drozda
23 Kodowanie – Algorytm KruskalaA = zbiór pusty dla każdego v V stwórz oddzielny zbiór posortuj krawędzie niemalejąco względem wag dla każdej krawędzi e według niemalejących wag jeśli u,v należą do różnych zbiorów A =A + {(u,v)} połącz zbiory z u i v dr Paweł Drozda
24 Wyszukiwanie najkrótszej ścieżkiWyznaczenie najkrótszych ścieżek o wspólnym początku Algorytm Dijkstry (zachłanny) dla grafów ważonych: wagi są nieujemne brak krawędzi oznaczany jest przez „odpowiednio dużą” wagę Q – zbiór wierzchołków, do których nie jest znana optymalna droga D – tablica z najmniejszymi odległościami od wierzchołka do źródła P – tablica zawierająca nr poprzedzającego wierzchołka na najkrótszej drodze dr Paweł Drozda
25 Algorytm Dijkstry 1 2 5 3 4 10 100 30 60 50 20 Dijkstra(G,s):foreach wierzchołek w begin d[w] = ∞; p[w] = -1; end d[s] = 0; Q = V; while ~empty(Q) do u = wyjmij_min(Q); foreach sasiad wierzcholka u alt = d[u]+koszt(u,sasiad); if alt
26 Algorytm Bellmana – FordaNajkrótsze ścieżki z jednego źródła Wagi mogą być ujemne p[] – tablica poprzedników d[] – odległość od źródła informuje czy da się wyznaczyć najkrótsze ścieżki – czy nie zawiera cykli ujemnych dr Paweł Drozda
27 Kodowanie – algorytm Bellmana - Fordadla każdego v V p[v] = nil d[v] = ∞ for i=1 to |V| - 1 dla każdej krawędzi e(u,v) E if d[v] > d[u] +w(u,v) d[v] = d[u] +w(u,v) p[v] = u if d[v] > d[u] +w(u,v) RETURN FALSE RETURN TRUE dr Paweł Drozda
28 Ścieżka Eulera Ścieżka przechodząca przez wszystkie krawędzie dokładnie raz Graf nieskierowany eulerowski – jeżeli wszystkie wierzchołki grafu (nieskierowanego) mają stopień parzysty, to da się skonstruować cykl Eulera półeulerowski – jeżeli najwyżej dwa wierzchołki mają nieparzysty stopień, to możliwe jest zbudowanie ścieżki Eulera Graf skierowany eulerowski – wszystkie wierzchołki z wyjątkiem dwóch mają takie same stopnie wychodzące i wchodzące półeulerowski – wszystkie wierzchołki z wyjątkiem dwóch mają takie same stopnie wychodzące i wchodzące, w jednym z tych dwóch wierzchołków stopień wychodzący jest o 1 większy niż wchodzący a w drugim odwrotnie dr Paweł Drozda
29 O(|V|+|E|)+O(|V|+|E|) = O(|V|+|E|)Algorytm Zbadać czy graf jest spójny Zbadać stopnie wierzchołków grafu Przejdź graf zaczynając od wierzchołka o nieparzystym stopniu (jeżeli jest) O(|V|+|E|)+O(|V|+|E|) = O(|V|+|E|) dr Paweł Drozda
30 Problem kojarzenia małżeństwGraf dwudzielny – graf, w którym możemy podzielić wierzchołki na 2 podzbiory tak, że nie istnieje krawędź łącząca 2 wierzchołki z tego samego podzbioru dr Paweł Drozda
31 Problem kojarzenia małżeństwProblem małżeństw jest rozwiązywalny, jeśli każdy podzbiór k panien, akceptuje jako przyszłych mężów co najmniej k kawalerów, gdzie k ≤ n. Filip Gustaw Henryk Igor Jan Anna Beata Celina Danuta Ewa dr Paweł Drozda