[Data Structure] #7-1 Graph - MST (Kruskal's Method)

신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 쉽게 말해 모든 정점이 연결되어 있어야 한다는 말이다. 만약에 N개의 정점이 있다면 N-1개의 간선만 존재하면 신장트리가 된다. 그 중에 MST(Minimum Spanning Tree)는 간선 비용의 총합이 가장 적은 트리를 의미한다.

참고로 MST 도 결국에는 Tree다. Tree는 connected acyclic graph로 모든 정점이 연결되어 있고 사이클이 없어야 한다. MST도 이러한 Tree의 특성을 물려받았다.

MST 를 구현하는 방법으로는 Kruskal 과 Prim 알고리즘이 있다. 여기서는 Kruskal만 정리한다.

Kruskal은 Sorting + Disjoint-Sets 이다..  자세한 것은 책이나 검색을 해보자.



Kruskal's Method


#include <iostream>
#define MAX_VERTICES 100
#define INF 100

using namespace std;

int parent[MAX_VERTICES];
int num[MAX_VERTICES];

/* Union_Find */

typedef struct {
int key; // 간선의 가중치
int u; // 정점1
int v; // 정점2
} element;

void SetInit(int n)
{
for (int i = 0; i < n; i++) {
parent[i] = -1;
num[i] = 1;
}
}

int SetFind(int vertex)
{
int p, s, i;
for (i = vertex; (p = parent[i]) >= 0; i = p);
s = i; // s 는 집합의 대표 원소가 된다
for (i = vertex; (p = parent[i]) >= 0; i = p)
parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정한다
return s;
}

void SetUnion(int s1, int s2)
{
if (num[s1] < num[s2]) {
parent[s1] = s2;
num[s2] += num[s1];
}
else {
parent[s2] = s1;
num[s1] += num[s2];
}
}

/* Heap */
element h[10000];
int hsize;

void Init()
{
hsize = 0;
}

void Insert(element item)
{
int i = ++hsize;
while ((i != 1) && item.key < h[i / 2].key)
{
h[i] = h[i / 2];
i /= 2;
}
h[i] = item;
}

element Remove()
{
int p, c;
element item = h[1];
element temp = h[hsize--];
p = 1;
c = 2;
while (c <= hsize)
{
if (c < hsize && 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;
}

void InsertHeapEdge(int u, int v, int weight)
{
element e;
e.u = u;
e.v = v;
e.key = weight;
Insert(e);
}

void InsertAllEdge()
{
InsertHeapEdge(0, 1, 29);
InsertHeapEdge(1, 2, 16);
InsertHeapEdge(2, 3, 12);
InsertHeapEdge(3, 4, 22);
InsertHeapEdge(4, 5, 27);
InsertHeapEdge(5, 0, 10);
InsertHeapEdge(6, 1, 15);
InsertHeapEdge(6, 3, 18);
InsertHeapEdge(6, 4, 25);
}

void Kruskal(int n)
{
int edge_accepted = 0; // 현재까지 선택된 간선의 수
int uset, vset; // 정점 u와 정점 v의 집합 번호
element e;

Init();
InsertAllEdge();
SetInit(n);
while (edge_accepted < (n - 1))
{
e = Remove();
uset = SetFind(e.u);
vset = SetFind(e.v);
if (uset != vset) {
printf("(%d,%d) %d \n", e.u, e.v, e.key);
edge_accepted++;
SetUnion(uset, vset);
}
}
}

int main()
{
Kruskal(7);
return 0;
}