Algorytm Kruskala
m |
m |
||
| Linia 1: | Linia 1: | ||
[[Kategoria:Algorytmy grafowe]] | [[Kategoria:Algorytmy grafowe]] | ||
| − | Algorytm | + | Algorytm Kruskala znajduje minimalne drzewo spinające w grafie z wagami na krawędziach. Wagi mogą być właściwie dowolnymi liczbami. |
Algorytm działa w czasie <var>m log(m) + n log<sup>*</sup> n</var>. | Algorytm działa w czasie <var>m log(m) + n log<sup>*</sup> n</var>. | ||
| Linia 7: | Linia 7: | ||
Oczywiście algorytm pomija krawędzie, których dodanie utworzy cykl spośród krawędzi już wcześniej dodanych. Aby wykryć czy dodana krawędź tworzy cykl, będziemy używać struktury [[UNION-FIND]] do łączenia zbiorów rozłącznych. | Oczywiście algorytm pomija krawędzie, których dodanie utworzy cykl spośród krawędzi już wcześniej dodanych. Aby wykryć czy dodana krawędź tworzy cykl, będziemy używać struktury [[UNION-FIND]] do łączenia zbiorów rozłącznych. | ||
| − | Poniżej znajduje się implementacja algorytmu | + | Poniżej znajduje się implementacja algorytmu Kruskala w języku C++. |
<table width="100%"> | <table width="100%"> | ||
<tr> | <tr> | ||
| Linia 84: | Linia 84: | ||
</table> | </table> | ||
| − | Algorytm | + | Algorytm Kruskala ma pewną zaletę, której nie ma [[Algorytm Prima-Dijkstry]]. Otóż algorytm ten nie musi pamiętać struktury całego grafu. Jego złożoność pamięciowa zależy tylko i wyłącznie od liczby wierzchołków. Ponadto algorytm Kruskala jest algorytmem on-line. Potrafi przetwarzać krawędzie podczas ich wczytywania. |
Wersja z 08:00, 28 lut 2008
Algorytm Kruskala znajduje minimalne drzewo spinające w grafie z wagami na krawędziach. Wagi mogą być właściwie dowolnymi liczbami.
Algorytm działa w czasie m log(m) + n log* n. Pierwszy składnik bierze się stąd, że algorytm sortuje wszystkie krawędzie według ich wag, a następnie dodaje do drzewa MST, które na początku jest zbiorem pustym kolejne. Sortowanie krawędzi odbywa się tylko raz. Algorytm rozpatruje bowiem kolejne krawędzie, zaczynając od najtańszych. Oczywiście algorytm pomija krawędzie, których dodanie utworzy cykl spośród krawędzi już wcześniej dodanych. Aby wykryć czy dodana krawędź tworzy cykl, będziemy używać struktury UNION-FIND do łączenia zbiorów rozłącznych.
Poniżej znajduje się implementacja algorytmu Kruskala w języku C++.
#include<algorithm> using namespace std; /* Rafał Nowak 2007.01.05 */ int tab[7000], ile[7000]; // 7000 - to liczba wszystkich elementów int Find(int a) { return (tab[a]==a) ? a : (tab[a] = fa); } bool Union(int a, int b) { int fa = Find(a); // szukaj reprezentanta zbioru zawierającego element 'a' int fb = Find(b); // szukaj reprezentanta zbioru zawierającego element 'b' if (fa==fb) return false; // nie trzeba nic łączyć if (ile[fa] <= ile[fb]) { ile[fb] += ile[fa]; tab[fa] = fb; } else { ile[fa] += ile[fb]; tab[fb] = fa; } return true; } pair< int,pair<int,int> > Edges[300000]; // tablica krawędzi do posortowania int main(void) { /* Na poczatku mamy n zbiorów rozłącznych : każdy ma jeden elelement {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9} */ int n, m, a,b,c,cost=0; scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { tab[i] = i; // reprezentantem zbioru zawierającego element // 'i' jest np 'i' (nikt inny być nie może :-) ile[i] = 1; // jeden element; chyba jasne, co nie? } for (int i=0; i<m; i++) { scanf("%d %d %d", &a, &b, &c); a--; b--;; Edges[i] = make_pair( c, make_pair(a,b) ); } sort(Edges, Edges+m); for (int i=0; i<m; i++) if ( Union(Edges[i].second.first,Edges[i].second.second) ) { cost += Edges[i].first; // krawędz drzewa : Edges[i].second.first -- Edges[i].second.second } printf("%d\n", cost); return 0; } |
|
Algorytm Kruskala ma pewną zaletę, której nie ma Algorytm Prima-Dijkstry. Otóż algorytm ten nie musi pamiętać struktury całego grafu. Jego złożoność pamięciowa zależy tylko i wyłącznie od liczby wierzchołków. Ponadto algorytm Kruskala jest algorytmem on-line. Potrafi przetwarzać krawędzie podczas ich wczytywania.
