Algorytm Kruskala

Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

Przykładowy kod:

#include <algorithm>
#include <vector>
 
using namespace std;
 
struct Krawedz
{
    int w1;
    int w2;
    int waga;
};
 
vector<Krawedz> krawedzie;
 
vector<int> ojciec, ranga;
 
void make_set (int x)
{
    ojciec[x] = x;
    ranga[x] = 0;
}
 
void link (int x, int y)
{
    if (ranga[x] > ranga[y])
        ojciec[y] = x;
    else
    {
        ojciec[x] = y;
        if (ranga[x] == ranga[y])
            ++ranga[y];
    }
}
 
int find_set (int x)
{
    if (x != ojciec[x])
        ojciec[x] = find_set(ojciec[x]);
 
    return ojciec[x];
}
 
void union (int x, int y)
{
    link(find_set(x), find_set(y));
}
 
bool compare (const Krawedz& ls, const Krawedz& rs)
{
    return ls.waga < rs.waga;
}
 
void kruskal ()
{
    sort(krawedzie.begin(), krawedzie.end(), compare);
 
    for (vector<Krawedzie>::const_iterator i = krawedzie.begin() ; i != krawedzie.end() ; ++i)
        if (find_set(i->v1) != find_set(i->v2)
            union(i->v1, i->v2);
}