Minimalne drzewo rozpinające

Algorytm Kruskala

Algorytm Prima

Rozważmy spójny graf nieskierowany G(V,E), którego każda krawędź posiada określoną dodatnią wagę, na przykład:

mst01.gif

(Tym razem dla większej przejrzystości rysunku, wierzchołki grafu oznaczyliśmy kolejnymi literami alfabetu.)

Naszym zadaniem jest znalezienie takiego podzbioru krawędzi, który zapewnia połączenie każdego wierzchołka grafu z dowolnym innym i ponadto posiada najmniejszą możliwą sumę wag krawędzi. Taki podzbiór w oczywisty sposób nie może zawierać żadnego cyklu, a zatem jest drzewem i musi zawierać dokładnie V-1 krawędzi dla grafu o V wierzchołkach. Drzewo takie z uwagi na minimalną sumę wag nazywane jest minimalnym drzewem rozpinającym (ang. minimum spanning tree), w skrócie MST.

Przedstawimy tutaj dwa podstawowe algorytmy znajdowania MST: algorytm Kruskala i algorytm Prima. Obydwa algorytmy są algorytmami zachłannymi i opierają się na następującym schemacie: na początku MST jest zbiorem pustym. Dopóki ilość jego elementów jest mniejsza od V-1, szukamy kolejnej „dobrej” krawędzi i dołączamy ją do MST. Co to znaczy, że krawędź jest „dobra”? Po pierwsze, taka krawędź nie może tworzyć cyklu z krawędziami już dołączonymi do MST. Po drugie – zgodnie z zasadami strategii zachłannej – musi to być krawędź o minimalnej wadze spośród dostępnych w danym momencie krawędzi. Wspomniane dwa algorytmy różnią się właśnie w sposobie wyboru tej „najlepszej” krawędzi.

Algorytm Kruskala

W tym algorytmie rozpoczynamy od posortowania wszystkich krawędzi według wag w porządku niemalejącym. Ponadto utworzymy V rozłącznych zbiorów wierzchołków na początku zawierających po jednym wierzchołku grafu. Dodając kolejne krawędzie, będziemy wybierać takie, które łączą dwa rozłączne zbiory w jeden zbiór. (Krawędzie w obrębie tego samego zbioru wierzchołków odrzucamy, gdyż utworzyłyby cykl.)

Prześledzimy działanie tego algorytmu na naszym przykładowym grafie. Najpierw sortujemy krawędzie, otrzymując następującą listę (kolejność krawędzi o tych samych wagach wybraliśmy arbitralnie):

FH AC BD EF AB CD CE BH EG DF AG GH

Jako pierwszą bierzemy krawędź FH, a jako drugą – AC:

mst02.gif

Kolejne dwie krawędzie to BD i EF:

mst03.gif

Teraz bierzemy krawędź AB, krawędź CD odrzucam (łączy nierozłączne zbiory wierzchołków) i w kolejności bierzemy CE:

mst04.gif

Krawędź BH odrzucamy i bierzemy krawędź EG, co kończy algorytm:

mst05.gif

Jak widać drzewo MST w fazie konstrukcji metodą Kruskala jest raczej zbiorem drzew (czyli lasem) niż pojedynczym drzewem, ale kiedy znajdą się już w nim wszystkie właściwe krawędzie, wtedy staje się spójnym drzewem.

Algorytm Kruskala możemy zaimplementować przy wykorzystaniu funkcji find znajdującej reprezentanta zbioru rozłącznego oraz funkcji union dokonującej połączenia dwóch zbiorów wierzchołków. Kolejną krawędź (a,b) z posortowanej listy akceptujemy, jeśli find(a) nie jest równe find(b). Jeśli krawędź jest „dobra”, wtedy wykonujemy operację połączenia zbiorów: union(find(a),find(b)). Działanie to powtarzamy, aż ilość zaakceptowanych krawędzi osiągnie wartość V-1. Przy odpowiedniej implementacji operacji na zbiorach rozłącznych złożoność tego algorytmu wynosi O(E lg V).

Algorytm Prima

Drugi z algorytmów znajdujących minimalne drzewo rozpinające wykorzystuje kolejkę priorytetową, w której umieszczone są wierzchołki grafu. Kolejność wierzchołków wyznaczona jest przez wartość najmniejszej wagi krawędzi (ang. weight), która łączy dany wierzchołek z tworzonym drzewem MST. Wartość tę nazywać będziemy key (ang. klucz). Wierzchołek o najmniejszym kluczu znajduje się na początku kolejki. Jeśli wierzchołek nie jest połączony z drzewem, wtedy jego wartość klucza przyjmujemy za nieskończenie wielką (∞). Dla każdego wierzchołka pamiętać będziemy ponadto, który wierzchołek jest jego poprzednikiem w tworzonym drzewie (ang. parent). Jeśli poprzednik nie został ustalony, wtedy przyjmujemy, że ma wartość nil.

Drzewo MST tworzone przy pomocy algorytmu Prima od samego początku jest pojedynczym drzewem (w przeciwieństwie do algorytmu Kruskala). Konstrukcję MST rozpoczynamy od dowolnie wybranego wierzchołka grafu i będziemy dołączać do drzewa kolejne „dobre” krawędzie: takie, które nie generują cyklu i posiadają minimalną wagę (co zapewni nam kolejka priorytetowa).

Dla przykładu rozważymy znowu następujący graf – konstrukcję MST rozpoczniemy od wierzchołka A:

mst01.gif

Pierwszy krok polega na zainicjalizowaniu tablicy kluczy i poprzedników (użyjemy literowych symboli wierzchołków od A do H):

for v=A to H do
   key[v] = ∞
   parent[v] = nil
key[A] = 0

Następnie wstawiamy wszystkie wierzchołki grafu do kolejki priorytetowej Q (na czele znajdzie się wierzchołek A z kluczem równym zero):

for v=A to H do
   Q.push(A)

Następnie przetwarzamy wierzchołki z kolejki, aż stanie się ona pusta:

while Q ≠ {∅}
   u = Q.front()
   process(u)

Funkcja front zwraca i zdejmuje czołowy element z kolejki.

Funkcja process(u) przegląda listę sąsiedztwa wierzchołka u (adj[u]) i jeśli trafi na wierzchołek v, który jeszcze czeka w kolejce (czyli nie należy jeszcze do MST) i któremu można zmniejszyć wartość klucza za pomocą krawędzi (u,v), to wtedy wykonuje zmianę jego klucza i ustawia wartość jego poprzednika na u:

process(u)
   foreach v ∈ adj[u]
      if v ∈ Q && weight(u,v) < key[v]
         key[v] = weight(u,v)
         parent[v] = u

Pierwszy wierzchołek zdejmowany z kolejki stanowi korzeń drzewa. Zdejmując każdy następny wierzchołek dodajemy do MST krawędź łączącą go z jego poprzednikiem.

Kolejka priorytetowa musi być tak zaimplementowana, aby zmiana klucza jej elementu automatycznie powodowała jego przesunięcie na właściwe miejsce. Można to zrobić przy użyciu kopca binarnego, co daje złożoność całego algorytmu taką samą, jak algorytmu Kruskala, czyli O(E lg V). Jeśli jednak kolejkę zbudujemy w oparciu o kopiec Fibonacci’ego, wtedy złożoność algorytmu Prima zmaleje do O(E + V lg V).

Prześledzimy teraz szczegółowo działanie tego algorytmu na naszym przykładowym grafie. Pierwsze wywołanie funkcji process przetwarza wierzchołek A, który ma sąsiadów B, C oraz G – każdy z nich ma klucz o nieskończonej wartości, zatem każdemu z nich nadajemy nową wartość klucza i poprzednika:

key[B] = 4   parent[B] = A
key[C] = 3   parent[C] = A
key[G] = 6   parent[G] = A

Teraz na czele kolejki jest wierzchołek C, zatem do MST dołączamy krawędź łączącą go z poprzednikiem (A):

mst06.gif

Funkcja process przegląda sąsiadów wierzchołka C: A, D oraz E. Wierzchołek A odpada, bo nie należy do kolejki, a pozostałe wierzchołki otrzymują nowe wartości kluczy i poprzednika:

key[D] = 6   parent[D] = C
key[E] = 5   parent[E] = C

Na czele kolejki jest teraz wierzchołek B z kluczem równym 4 i poprzednikiem A, zatem do MST dołączamy krawędź AB:

mst07.gif

Lista sąsiadów wierzchołka B zawiera dwa wierzchołki, które czekają w kolejce: D (z kluczem 6) oraz H (z kluczem nieskończonym). Wykonujemy zatem operacje:

key[D] = 3   parent[D] = B
key[H] = 5   parent[H] = C

i wierzchołek D przesuwa się na czoło kolejki. Zdejmując go z kolejki dodajemy krawędź BD:

mst08.gif

Jedynym jego sąsiadem pozostającym w kolejce jest wierzchołek F, zatem mamy:

key[F] = 6   parent[F] = D

Na czele kolejki znajduje się wierzchołek E z kluczem równym 5 i poprzednikiem C, a więc dołączamy krawędź CE:

mst09.gif

Wierzchołek E posiada dwóch sąsiadów z kolejki, którym może poprawić klucze:

key[F] = 3   parent[F] = E
key[G] = 4   parent[G] = E

Teraz na czele mamy wierzchołek F z kluczem 3 i poprzednikiem E, wiec dołączamy krawędź EF:

mst10.gif

Możemy zmniejszyć teraz klucz wierzchołka H:

key[H] = 2   parent[H] = F

Tym samym wierzchołek H przesuwa się na czoło kolejki, zatem dodajemy krawędź FH:

mst11.gif

W kolejce pozostał już tylko wierzchołek G z poprzednikiem E, zatem dołączamy krawędź EG, co kończy algorytm:

mst12.gif

Powrót do Algorytmy zachłanne

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License