1 ALGORYTMY I STRUKTURY DANYCHWYKŁAD 11 Algorytmy na grafach - metoda zachłanna Grażyna Mirkowska PJWSTK, semestr letni 2003

2 G. Mirkowska, ASD_11 Algorytmy na grafachPlan wykładu Idea algorytmów zachłannych Problem drzew rozpinających Chodzenie po grafie ze stosem i kolejką Algorytm Kruskala Problem najkrótszych ścieżek Algorytm Dijksty maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

3 G. Mirkowska, ASD_11 Algorytmy na grafachNa czym to polega? „Greedy” algorithms ZASADA W każdym kroku, w którym trzeba dokonać wyboru, wybierać zawsze rozwiązanie lokalnie optymalne, takie które w danym momencie działania algorytmu jest najlepsze. maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

4 G. Mirkowska, ASD_11 Algorytmy na grafachDrzewa rozpinające Niech G będzie dowolnym grafem niezorientowanym . Drzewem rozpinającym grafu G = nazywamy graf G* = taki, że (1) V* = V, E*  E (2) G* jest drzewem (tzn. grafem spójnym i acyklicznym). Definicja Graf i jego drzewa rozpinające maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

5 Jak znaleźć drzewo rozpinające grafu (1)?BFS Włóż do kolejki wybrany wierzchołek grafu i zamarkuj go. Dopóki kolejka nie jest pusta 1. Weź pierwszy element z kolejki i dopisz do kolejki wszystkie wierzchołki z nim incydentne, o ile nie były zamarkowane i zamarkuj je. 2. Wypisz krawędzie, po których przeszedłeś do nowych wierzchołków. 3. Usuń pierwszy element z kolejki. a b c d e f a a b f f b c e c e f c e d ab af bc be c d e d Wynik: d maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

6 Jak znaleźć drzewo rozpinające grafu(2)?DFS Włóż na stos wybrany wierzchołek grafu i zamarkuj go. Dopóki stos nie jest pusty : 1. Weź element ze szczytu stosu. 2 . Usuń ze stosu ten element. 3. Dopisz do stosu wszystkie wierzchołki z nim incydentne, których jeszcze nie zamarkowano, a dopisane wierzchołki zamarkuj. 4. Wypisz krawędzie, po których przeszedłeś do wierzchołków zamarkowanych w p.3. a b c d e f e d f c b c b c a b b b ab a f e d f c fe Wynik: maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

7 Minimalne drzewo rozpinająceNiech będzie dany graf G = spójny niezorientowany, skończony i niech c : E  R+ będzie funkcją kosztu określoną na krawędziach tego grafu. Problem Dla danego skończonego grafu G oraz danej funkcji kosztu c, znaleźć minimalne drzewo rozpinające, tzn. takie drzewo rozpinające grafu G, że suma kosztów jego krawędzi S eT c (e) jest najmniejsza. maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

8 Przykład: sieć wodociągowa1 4 6 7 5 3 2 10 8 15 9 1 4 6 7 5 3 2 10 8 15 9 Jakieś drzewo rozpinające Minimalne drzewo rozpinające maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

9 G. Mirkowska, ASD_11 Algorytmy na grafachLemat {Vi: 1 i  k}= V Ti  E dla 1 i  k Vi  Vj =  dla i j di - drzewo Niech G = będzie grafem spójnym, skończonym i niech c będzie jego funkcją kosztu. Niech d1= , d2= ,......, dk = będzie danym lasem rozpinającym G Vi Niech e = (v,w) będzie krawędzią o minimalnym koszcie, która nie należy do żadnego z drzew di. v Dowód przez sprowadzenie do sprzeczności: Przypuśćmy, że istnieje takie drzewo do ktorego krawędz e nie nalezy i którego koszt jest minimalny. Ponieważ w tym drzewie musi istniec droga od v do w to nie przechodzi ona przez krawędz e. Zatem weżmy na tej drodze dwa wierzchołki sąsiednie jeden ze zbioru Vi a drugi nie należący do Vi. Wtedy krawędź (v', w') ,która nie należała do żadnego z drzew danych musi mieć koszt większy niz e. Zastępując krawędź (v',w') krawędzią e otrzymamy drzewo rozpinające o koszcie mniejszym niż wybrane. Sprzeczność. v’ Nie istnieje drzewo rozpinające grafu G, takie że e T* oraz ma najmniejszy koszt wśród drzew rozpinających zawierających wszystkie Ti. w w’ Ale c(v’,w’) > c(v,w) maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

10 G. Mirkowska, ASD_11 Algorytmy na grafachAlgorytm 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. 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ć. Algorytm maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

11 G. Mirkowska, ASD_11 Algorytmy na grafachPrzykład 1. (1,2) 2. (1,4) 3.(2,3) 4. (1,3) 5.(4,5) 6. (3,5) 7. (1,5) 7. (6,7) 8. (1,6) 10. (7,4) 15. (4,3) + 5 2 3 4 7 1 6 15 8 10 1| 2| 3| 4| 5| 6| 7 + 1, 2| 3| 4| 5| 6| 7 + 1, 2, 4| 3| 5| 6| 7 1, 2, 3, 4| 5| 6| 7 + 1, 2, 3, 4, 5| 6| 7 + 1, 2, 3, 4, 5| 6, 7 + 1, 2, 3, 4, 5, 6, 7 + Kolejka Priorytetowa Podział maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

12 Algorytm Zakładam, że 1. pq jest kolejką priorytetową wszystkich krawędzi danego grafu G = , P jest początkowym podziałem zbioru V, T pustym stosem (będą tam krawędzie drzewa). { while (not empty (pq) and card(P)>1) do kr := min(pq); pq := delmin(pq); A := Find(P,kr.początek); B := Find(P,kr.koniec); if A B then P := Union(P,B,A); T := push(T,kr) fi od } Find (P,x) = ten zbiór podziału P do którego należy x Union(P,B,A) = podział powstający z P przez połączenie zbiorów A i B. maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

13 Jak to zaimplementować?Struktura Find-Union Drzewa z balansowaniem i kompresją ścieżek A A A B Koszt utworzenia kolejki priorytetowej – O(m lg m) Koszt 2m operacji Find O(lg(n)) Koszt m operacji Union O(1) Koszt Razem O(m lg n) maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

14 Problem Problem ścieżekDany jest graf G = i jego funkcja kosztu c : E  R +. Problem Znaleźć najkrótsze drogi od ustalonego wierzchołka (źródła) do wszystkich innych wierzchołków. 1 4 6 7 5 3 2 10 8 15 Suma kosztów krawędzi leżących na tej drodze jest najmniejsza maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

15 G. Mirkowska, ASD_11 Algorytmy na grafachMetoda Dijkstry W kolejnych etapach algorytmu zbiór wierzchołków osiągalnych ze źródła jest powiększany o wierzchołki incydentne z ostatnio dołączonymi. Zawsze staramy się by dołączać te wierzchołki, których osiągnięcie wymaga najmniejszego kosztu (które znajdują się „najbliżej” zródła). maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

16 G. Mirkowska, ASD_11 Algorytmy na grafachStruktura danych Tablica d (1: n) d[i] = długość najkrótszej ścieżki miedzy źródłem s, a wierzchołkiem i. Na początku d[i] = c(s,i), jeśli (s,i) E, d[i] = + w p.p. Tablica P(1:n) P[i] = ojciec wierzchołka i na najkrótszej ścieżce od s do i. Zbiór wierzchołków S1 osiągalnych z s. Na początku S1 = {s}. Zbiór S2 wierzchołków osiągalnych z S1, S2 = {y : istnieje x  S1, że (x,y)  E}. Na początku S3 = V-{s}. Zbiór wierzchołków S3, których jeszcze nie sklasyfikowano. maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

17 G. Mirkowska, ASD_11 Algorytmy na grafachPrzykład A B C D E F G H I 2 5 4 1 6 9 3 A S2 S1 A B G F S1 A F G B C A B C D E F G H I J d P 2 6 9 5 A B A A maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

18 G. Mirkowska, ASD_11 Algorytmy na grafachc.d. przykładu A B C D E F G H I 2 5 4 1 6 9 3 S2 B C S1 A G H I S1 A F G B C I H S2 F D A B C D E F G H I J d P 2 6 8 9 5 10 7 A B C A A G G maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

19 G. Mirkowska, ASD_11 Algorytmy na grafachCd. przykładu S2 A B C D E F G H I 2 5 4 1 6 9 3 C B D S1 A G I H F A B C D E F G H I J d P 2 6 8 9 5 10 7 Itd A B C A A G G maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach

20 G. Mirkowska, ASD_11 Algorytmy na grafach{x := s; while niepusty (S3) do Dla wszystkich wierzchołków y incydentnych z x do case y  S if d(x) +c(x,y) Koszt Algorytmu Dijkstry O(card(V)2) maj 2003 G. Mirkowska, ASD_11 Algorytmy na grafach