« poprzedni punkt   następny punkt »


4. Algorytm Kruskala

Specyfikacja problemu

Dany jest graf niezorientowany G = <V, E> i funkcja przypisująca krawędziom grafu liczby rzeczywiste, c: E ® R+. Znalezć minimalne drzewo rozpinajce tego grafu, tzn. acykliczny, spójny podgraf tego grafu, którego zbiorem wierzchołków jest V, a zbiór krawędzi jest zawarty w zbiorze E i taki, że suma kosztów krawędzi jest minimalna.

Jednym z możliwych rozwiązań tego problemu jest algorytm Kruskala, który w pełni wykorzystuje ideę kostrukcji drzewa rozpinajcego zawartą w twierdzeniu 3.1. Przypomnijmy jeszcze raz: jeśli drzewo rozpinające ma mieć koszt minimalny i rozrzerzać dany las rozpinający, to musi zawierać krawędź o najmniejszym koszcie wśród tych, które nie należą do lasu rozpinającego i łączą wierzchołki dwóch różnych drzew.

Idea algorytmu

Zaczynamy od lasu rozpinającego, złożonego z n drzew (jego koszt wynosi zero, jest więc najmniejszy z możliwych). W każdym następnym kroku alorytmu zmniejszamy liczbę drzew przez dołączenie nowej krawędzi o minimalnym koszcie, łączącej dwa (różne) drzewa aktualnie istniejącego lasu rozpinającego.

Nie znając jeszcze szczegółów algorytmu, możemy powiedzieć, że zastosowana metoda rozwiązania jest metodą zachłanną. Wybierając w każdym kroku krawędź o minimalnym koszcie, zapewniamy optymalność rozwiązania w danej chwili: koszt otrzymanego lasu rozpinającego jest minimalny wśród wszystkich możliwych lasów rozpinających tego grafu o tej samej liczbie drzew składowych .

Algorytm Kruskala ma bardzo złożoną strukturę danych: musimy pamiętać aktualnie znaleziony las rozpinający i modyfikować go. Zauważmy, że nie musimy pamiętać każdego z drzew lasu rozpinającego osobno. Wystarczy zapamiętać zbiory wierzchołków tych drzew, czyli podział zbioru V, oraz zbiór wszystkich krawędzi występujących lesie.  Przyjmijmy, że wybrane w algorytmie krawędzie  będziemy przechowywać na stosie. W ten sposób po zakończeniu działania algorytmu, wynik - drzewo rozpinające, będziemy mogli odczytać z tego stosu. Ponieważ, zgodnie z ideą algorytmu, trzeba wielokrotnie wybierać krawędź o minimalnym koszcie, uporządkujmy wszystkie krawędzie grafu rosnąco, umieszczając je w kolejce priorytetowej. Jeśli dwie krawędzie mają przypisany ten sam koszt, to porządek tych krawędzi można ustalić dowolnie. Od niego jednak zależy jakie ostatecznie drzewo rozpinajce otrzymamy.

Przyjrzyjmy się jeszcze operacjom, jakie trzeba wykonywać w związku z modyfikacjami lasu rozpinającego. Dołączenie nowej krawędzi łączącej dwa drzewa, spowoduje połączenie dwóch drzew w jedno. Jeśli pamiętamy tylko podział zbioru wierzchołków, to musimy wykonać operację sumy teoriomnogościowej zbiorów tego podziału (operacja Union). Aby jednak móc tę operację wykonać, musimy wcześniej wiedzieć, z jakich to zbiorów podziału pochodzą końce wybranej krawędzi (operacja Find).
Niech 

Te dwie operacje na podziałach omówimy osobno w punkcie piątym tego wykładu.

Algorytm

Niech G będzie grafem spójnym, niezorientowanym o n wierzchołkach i m krawędziach. Niech s będzie początkowo pustym stosem, a pq kolejką priorytetową. Obiektami umieszczanymi na stosie i w kolejce prioytetowej będą krawędzie. Zakładamy, że dla każdej z nich określone są trzy atrybuty:

 c -  koszt krawędzi,   oraz Lend i Rend - wierzchołki,  będące końcami tej krawędzi.

Kruskal
 (G: graph){

Utwórz kolejkę priorytetową wszystkich krawędzi grafu G

Utwórz początkowy podział P zbioru V,   P= {{v} : v ÎV}

while not empty(pq)  do

      e := min(pq);                                    \\wybieramy krawędź o minimalnym koszcie

      pq := delmin(pq);

      A := Find(P, e.Lend);                       \\ znajdujemy  zbiory, do których należą końce krawędzi

      B := Find(P, e.Rend);                      

      if ¬ A = B then                         

             P := Union(P,A,B);                      \\jeśli zbiory A i B są różne, to łączymy je

             s := push(s,e)                                \\ i dopisujemy do stosu wybraną krawędź

    fi 

od }


Poprawność algorytmu Kruskala

Zauważmy najpierw, że pętla while w tym algorytmie pozwala wybrać n-1 różnych krawędzi. Ponieważ z założenia graf jest spójny, zatem ma co najmniej n-1 krawędzi, a więc kolejka priorytetowa, utworzona w pierwszym punkcie algorytmu, zawiera co najmniej n-1 elementów. Jeżeli zbiory A i B są identyczne, tzn. krawędź e łączy wierzchołki należące do tego samego drzewa w aktualnym lesie drzew, to dołączenie tej krawędzi jest niemożliwe, bo spowodowałoby powstanie cyklu. Jeśli zbiory A i B są różne, to ich połączenie krawędzią e spowoduje powstanie nowego drzewa, którego zbiorem wierzchołków jest suma teoriomnogościowa zbiorów wierzchołków obu drzew. Otrzymamy więc nowy podział zbioru wierzchołków grafu, podział, w którym liczba drzew jest o jeden mniejsza niż w P. Oczywiście po co najwyżej m iteracjach,  w podziale P będzie się znajdował tylko jeden zbiór zawierający wszystkie wierzchołki, a zbiór krawędzi na stosie będzie tworzył drzewo rozpinające grafu G.
Niezmiennikiem pętli jest tu formuła mówiąca, że rodzina zbiorów podziału P wraz ze zbiorem krawędzi znajdujących się na stosie, tworzy las rozpinający  grafu G .
Koszt zbudowanego drzewa rozpinającego jest minimalny, bo gwarantuje to nam twierdzenie 3.1. Ostatecznie możemy sformułować twierdzenie:

Twierdzenie 4.1  Algorytm Kruskala jest poprawnym rozwiązaniem problemu znalezienia minimalnego drzewa rozpinającego niezorientowanego grafu spójnego. 

Koszt algorytmu Kruskala istotnie zależy od sposobu realizacji operacji Find i Union i wrócimy do tego problemu na zakończeniu punktu piątego. Teraz przypomnijmy tylko, że jeśli kolejka priorytetowa została zaimplementowana jako kopiec, to koszt związany z jej utworzeniem wynosi O(m lgm), gdzie m jest liczbą krawędzi grafu G.  Pętlę "while" moglibyśmy w niektórych przypadkach skrócić, gdybyśmy dodatkowo zliczali liczbę wybranych krawędzi lub gdybyśmy pamiętali liczbę drzew w lesie rozpinającym.

Przykład 4.1

Na rysunku 12.7 przedstawiono graf i kolejne stany budowy jego drzewa rozpinającego.  Przyjęliśmy, że o kolejności krawędzi  o tym samym koszcie w kolejce prirytetowej decyduje porządek leksykograficzny w zbiorze wierzchołków grafu. Znakiem + oznaczyliśmy kolejno wybierane krawędzie. Po prawej stronie rysunku, w kolejnych wierszach zaznaczono podziały zbioru wierzchołków.  Zbioru podziału są umieszczone w osobnych klatkach tablicy. Ostateczny wynik - minimalne drzewo rozpinające grafu było przedstawione na rysunku 12.2(b).


Kolejka
priorytetowa

Podział zbioru wierzchołków
A
 B
 C
 D
 E
 F
 G
 H
 I
1.
 ED
 1
 +
 A
 B
 C
 DE
 F
 G
 H
 I
2.
 FI
 1
 +
 A
 B
 C
 DE FI G
3.
 DH
 1
 +
 A
 B
 C
 DEH
 FI G
4.
 AB
 2
 +
 AB C
 DEH FI G
5.
 CD
 2
 +
 AB CDEH FI G
6.
 GI
 2
 +
 AB CDEH FGI
7.
 EI
 3
 +
 AB
 CDEFGHI
8.
 BC
 4
 +
 ABCDEFGHI
9.
 IH
 4
  








10.
 AG 5









11.
 CH 5









12.
 GH 5









13.
 BG 6









14.
 EF 6


Rysunek 12.7



15
 AF 9











Pytanie 6: Czy koszt utworzenia kolejki priorytetowej w algorytmie Kruskala zastosowanym do grafu  G=<V,E>  niezorientowanego spójnego  można oszacować przez O(m lg n) ?



« poprzedni punkt   następny punkt »