[Algorithm] Kruskal Algorithm

Kruskal 알고리즘은 MST를 만들어내는 알고리즘 하나로서 Heap과 Union-Find 라는 자료구조를 이용한다. Greedy 알고리즘이라 최적해를 도출해 내는지 알 순 없지만 누군가 증명을 했단다. MST를 이용하면 Minimum Spanning Tree 가 만들어진다.


#include <iostream>
#include <stdio.h>
#define MAX_VETICES 100
using namespace std;

// Kruskal's element
typedef struct
{
int key;
int u;
int v;
} k_elem;

// Union-Find
int parent[MAX_VETICES];
int num[MAX_VETICES];
void set_init(int n)
{
for (int i = 0; i < n; i++){
parent[i] = -1;
num[i] = 1;
}
}
int set_find(int v)
{
int p, i = -1;
for (i = v; (p = parent[i]) >= 0; i = p);
int s = i;
for (i = v; (p = parent[i]) >= 0; i = p){
parent[i] = s;
}
return s;
}
void set_union(int s1, int s2)
{
int p1 = set_find(s1);
int p2 = set_find(s2);
if (num[p1] > num[p2]){
parent[p2] = p1;
num[p1] += num[p2];
}
else{
parent[p1] = p2;
num[p2] = parent[p1];
}
}

// MinHeap
k_elem h[MAX_VETICES];
int h_size;
void h_init()
{
h_size = 0;
}
void h_insert(k_elem v)
{
int i = ++h_size;
while (i != 1 && v.key < h[i/2].key){
h[i] = h[i / 2];
i /= 2;
}
h[i] = v;
}
k_elem h_remove()
{
k_elem item = h[1];
k_elem temp = h[h_size--];
int p = 1;
int c = 2;
while (c <= h_size){
if (h[c].key > h[c + 1].key) c++;
if (temp.key <= h[c].key) break;
h[p] = h[c];
p = c;
c *= 2;
}
h[p] = temp;
return item;
}

// Kruskal
int k_distance[MAX_VETICES][MAX_VETICES] =
{
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 29, 0, 0, 0, 10, 0 }, // a
{ 0, 29, 0, 16, 0, 0, 0, 15 }, // b
{ 0, 0, 16, 0, 12, 0, 0, 0 }, // c
{ 0, 0, 0, 12, 0, 22, 0, 18 }, // d
{ 0, 0, 0, 0, 22, 0, 27, 25 }, // e
{ 0, 10, 0, 0, 0, 27, 0, 0 }, // f
{ 0, 0, 15, 0, 18, 25, 0, 0 }, // g
};


void kruskal(int n)
{
h_init();
set_init(n);
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++){
if (k_distance[i][j] > 0){
k_elem element{ k_distance[i][j], i, j };
h_insert(element);
}
}
}

int accepted = 0;

while (accepted < (n - 1)){
k_elem e = h_remove();
int uset = set_find(e.u);
int vset = set_find(e.v);
if (uset != vset){
printf("(%d, %d) : %d\n", e.u, e.v, e.key);
accepted++;
set_union(uset, vset);
}
}
}


int main()
{
int n = 7;
kruskal(n);
return 0;
}