Algorytm Kruskala

RNO-Wiki

Algorytm Kruskala znajduje minimalne drzewo spinające w grafie z wagami na krawędziach. Wagi mogą być właściwie dowolnymi liczbami.

Algorytm zaczyna od pustego drzewa i zachłannie dodaje do niego kolejne krawędzie. Zachłanność polega na wybieraniu krawędzi o najmniejszych wagach. W tym celu algorytm najpierw sortuje wszystkie krawędzie po ich wagach, a następnie próbuje je dodawać do drzewa, pomijając oczywiście te krawędzie, które utworzą cykl. Do tego właśnie algorytm wykorzystuje strukturę UNION FIND. Algorytm ma złożoność czasową m log(m) + n log* n.

Poniżej znajduje się implementacja algorytmu Kruskala w języku C++. 

#include<algorithm>
using namespace std;
/*
	Rafał Nowak ,  www.rafalnowak.pl
	2008.02.27
*/
int tab[7000], ile[7000]; // 7000 - to liczba wszystkich elementów
 
int Find(int a) { return (tab[a]==a) ? a : (tab[a] = Find(tab[a])); }
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.

Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=Algorytm_Kruskala"