<Kruskal의 MST 알고리즘> 기본개념과 알고리즘

# Kruskal의 MST 알고리즘

---

 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에 있어 중요한 기법 중 하나다. 결정을 해야 할 때, 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 방법을 말한다. 순간 순간의 최선을 선택해 최종적인 해답에 도달하는 과정인 것이다.

 당시에 최적이라고 생각했던 선택들을 모은다고 해서 최종적인 결과가 최적의 해답이라는 보장은 없다. 따라서 탐욕적인 방법은 항상 검증이 필요하다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.

 Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건을 기초로 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. // 최소 비용 간선이란, n개의 정점을 가진 그래프가 n - 1개의 간선을 가진다는 의미다. 가장 적은 간선을 이용하여 정점들을 모두 잇는다고 해서 최소 비용 간선이며 n - 1개보다 더 작은 간선을 이용해서 n개의 정점을 잇는 방법은 없다.

 Kruskal의 알고리즘은 먼저 그래프의 e개의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하면 그 간선은 제외된다. 크루스칼 알고리즘이 어떻게 작동하는지 아래의 과정을 통해 살펴보자.

 Kruskal의 알고리즘은 최소 비용 신장 트리를 구하는 다른 알고리즘보다 간단해 보인다. 하지만 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지를 체크하여야 한다. 새로운 간선이 이미 다른 경로에 의하여 연결되어 있는 정점들을 연결할 때 사이클이 형성된다. 

 간선의 양끝 정점이 같은 집합에 속한다면 간선을 추가할 때 사이클이 형성된다. 하지만 양끝 정점이 서로 다른 집합에 속하는 경우 두 정점을 연결하여도 사이클이 형성되지 않는다. 따라서 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사해야 한다. 이 검사를 위한 알고리즘을 union-find 연산(알고리즘)이라 부른다.

# Union Find 연산

---

 union-find 연산은 Kruskal 알고리즘에서만 사용되는 것이 아니라 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해 있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x) 연산은 원소 x가 속해 있는 집합을 반환한다.

 예를 들어 S = { 1, 2, 3, 4, 5, 6 }의 집합을 가정하자. 먼저 집합의 원소를 하나씩 분리하여 독자적인 집합으로 만든다.

{ 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }

 여기에 union(1, 4)와 union(5, 2)를 하면 다음과 같은 집합으로 변화한다.

{ 1, 4 }, { 5, 2 }, { 3 }, { 6 }

또한 이어서 union(4, 5)와 union(3, 6)을 한다면 다음과 같은 결과를 얻을 수 있다.

{ 1, 4, 5, 2 }, { 3, 6 }

 집합을 구현하는데는 여러가지 방법이 있을 수 있다. 비트 벡터, 배열, 연결 리스트 등을 이용하여 구현할 수 있다. 그러나 가장 효율적인 방법은 트리를 이용하는 것이다. 각 집합을 그 집합에 들어 있는 원소들의 트리로 표현한다. 집합은 트리의 루트에 의하여 대표된다. 예를 들어 집합 { 1, 4 }, { 5, 2 }, { 3 }, { 6 } 들은 아래의 그림의 (a) 와 같이 표현되고, 이어서 union(4, 5)와 union(3, 6)을 한다면 (b)와 같은 트리로 변화한다. 이 상태에서 find(4)를 한다면 루트인 정점 2가 집합의 대표로 반환된다.

find 연산에 소요되는 시간을 줄이려면 특정 정점과 루트와의 거리가 짧아야 한다. 모든 정점이 루트 아래에 있도록 구성한다면 소요시간을 줄일 수 있을 것이다. 이를 위하여 find 연산이 이루어질 때마다 모든 원소를 루트 노드 바로 밑에 놓는다. 또한 union 연산 시에 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 한다.

 따라서 아래의 구현은 위 2가지를 염두에 두고 집합의 연산을 구현한 것이다. 여기서 트리는 포인터로 구현되는 것이 아니고 배열의 인덱스로 구현되어 있다. 배열의 인덱스를 포인터처럼 생각해본다. 트리는 부모의 정점을 가리키는 배열과 각 트리의 크기를 가지고 있는 배열 2개로 구성된다. 루트 정점은 부모 배열에서 -1을 가진다. // 루트의 부모는 없으므로 그 없는 정보를 단순히 -1로 표현하는 것뿐이다.

/*************************************************
 ** Union Find 연산의 구현
*************************************************/

int parent[MAX_VERTICES];	// 각 정점의 부모 노드
int num[MAX_VERTICES];		// 각 집합의 크기

// 초기화
void set_init(int n)
{
	int i;
	
	// 0 ~ n-1 인덱스까지 부모노드 배열은 모두 -1로
	// 집합의 크기 배열은 모두 1로 초기화한다.
	for (i = 0; i < n; i++)
	{
		parent[i] = -1;
		num[i] = 1;
	}
}

// 정점(vertex)이 속하는 집합을 반환한다.
int set_find(int vertex)
{
	int p, s, i = -1;	// p: 부모노드

	// 루트노드까지 반복한다. p가 -1이 되면 반복문은 종료한다.
	// p가 -1이라는 건 현재 노드(i)가 루트라는 뜻이다.
	for (i = vertex; (p = parent[i]) >= 0; i = p);

	s = i;	// 루트노드 정보를 s에 저장

	// 모든 노드들(i로 순회)의 부모가 s(루트 노드)에 되도록 설정한다.
	for (i = vertex; (p = parent[i]) >= 0; i = p)
		parent[i] = s;

	return s;	// 모든 노드의 부모인 루트를 반환한다.
}

// 두 개의 원소의 크기 정보 s1, s2를 받아 두 집합을 합친다.
void set_union(int s1, int s2)
{
	// 더 큰 쪽을 기준으로 집합을 합친다.
	if (num[s1] < num[s2])
	{
		// 집합 s2가 더 크다면
		parent[s1] = s2;	// s1의 부모를 s2로 설정
		num[s2] += num[s1]; // s2의 크기를 s1만큼 더해준다.
	}
	else
	{
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}

/*************************************************
 ** End Line
*************************************************/

# Kruskal 알고리즘의 구현

---

 위의 union 연산과 find 연산을 이용하여 Kruskal의 알고리즘을 구현해보면 아래와 같다. Kruskal 알고리즘에서는 간선들을 정렬하여야 하므로 최소 히프를 사용했다. 아래 프로그램이 그리고 있는 그래프는 위쪽에서 크루스칼 알고리즘의 작동원리를 설명할 때 사용했던 그래프다.

/*************************************************
 ** 최소히프를 이용한 Kruskal 알고리즘 (union find 포함)
*************************************************/

#include 

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100	// 그래프의 정점의 개수
#define INF 1000			// 경로가 존재하지 않음을 뜻함
#define MAX_ELEMENT 100		// 히프의 최대크기

/* union find*/
int parent[MAX_VERTICES];	// 각 정점의 부모 노드
int num[MAX_VERTICES];		// 각 집합의 크기

// 초기화
void set_init(int n)
{
	int i;
	
	// 0 ~ n-1 인덱스까지 부모노드 배열은 모두 -1로
	// 집합의 크기 배열은 모두 1로 초기화한다.
	for (i = 0; i < n; i++)
	{
		parent[i] = -1;
		num[i] = 1;
	}
}

// 정점(vertex)이 속하는 집합을 반환한다.
int set_find(int vertex)
{
	int p, s, i = -1;	// p: 부모노드

	// 루트노드까지 반복한다. p가 -1이 되면 반복문은 종료한다.
	// p가 -1이라는 건 현재 노드(i)가 루트라는 뜻이다.
	// 우리는 위에서 루트노드의 부모는 -1로 설정했다.
	for (i = vertex; (p = parent[i]) >= 0; i = p);

	s = i;	// 루트노드 정보를 s에 저장

	// vertex의 조상노드들이 s(루트 노드)를 향하게끔 설정한다.
	for (i = vertex; (p = parent[i]) >= 0; i = p)
		parent[i] = s;

	return s;	// 모든 노드의 부모인 루트를 반환한다.
}

// 두 개의 원소의 크기 정보 s1, s2를 받아 두 집합을 합친다.
void set_union(int s1, int s2)
{
	// 더 큰 쪽을 기준으로 집합을 합친다.
	if (num[s1] < num[s2])
	{
		// 집합 s2가 더 크다면
		parent[s1] = s2;	// s1의 부모를 s2로 설정
		num[s2] += num[s1]; // s2의 크기를 s1만큼 더해준다.
	}
	else
	{
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}

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

typedef struct
{
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

void init(HeapType *h)
{
	h->heap_size = 0;
}

int is_empty(HeapType *h)
{
	if (h->heap_size == 0)
		return TRUE;
	else
		return FALSE;
}

void insert_min_heap(HeapType *h, element item)
{
	int i = ++(h->heap_size);

	/* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
	// i가 루트가 아니고 입력으로 받은 item의 key값이 i의 부모의 키 값보다 작으면
	while ((i != 1) && (item.key < h->heap[i / 2].key))
	{
		// 거슬러올라가야 하므로 현재노드를 부모노드로 설정하고
		h->heap[i] = h->heap[i / 2];

		// 인덱스를 부모노드의 인덱스로 설정한다.
		i /= 2;
	}
	// 탈출했다는 건 더이상 거슬러 올라갈 곳이 없다는 것이므로
	// 현재 인덱스의 위치에 item을 삽입한다.
	h->heap[i] = item;
}

element delete_min_heap(HeapType *h)
{
	int parent, child;
	element item, temp;

	// 최소히프의 특성상 루트노드에 있는 값이 가장 작은값이므로
	// 반환할 루트노드의 값을 item에 저장해둔다.
	item = h->heap[1];

	// 맨 마지막에 있는 노드의 값을 temp에 저장하고
	// 루트노드의 정보를 위에서 빼냈으므로 힙사이즈를 1 줄인다.
	temp = h->heap[(h->heap_size)--];

	/* 맨 마지막 노드값 (temp)를 이용한 비교과정 */
	// temp를 일단 루트에 두었다고 가정하고 아래 과정을 시작한다.
	// 최소히프 삭제는 루트노드부터 말단으로 가며 차례대로 비교하여
	// 적절한 위치를 찾아 삽입하는 작업이다.

	parent = 1; // 맨 첫 실행의 부모노드를 루트로 둔다.
	child = 2; // 그리고 그 왼쪽 자식을 자식노드로 둔다.

	// child가 힙 사이즈보다 크면 힙을 벗어난 비교이므로 실행이 안된다.
	// 따라서 child가 힙 사이즈보다 작거나 같을 때 비교가 일어난다.
	while (child <= h->heap_size)
	{
		// 두 개의 자녀 중 더 작은 자녀를 비교기준으로 삼기 위해 아래의 if문 실행
		if (
			// 오른쪽 자녀가 있다고 생각하면, child는 힙사이즈보다 작아야 한다.
			// 왼쪽 자녀가 힙사이즈와 같은데 오른쪽 자녀가 있다면 + 1을 해줘야 하는데
			// 그렇게 되면 힙사이즈를 넘어서기 때문에 child는 힙사이즈보다 작아야 한다.
			(child < h->heap_size) && 
			// 오른쪽 자녀 (child + 1)이 더 작기 때문에 새로운 기준점을 만들어주기 위해
			// child++ 을 해준다.
			(h->heap[child].key) > h->heap[child + 1].key
			)
			child++;

		// 비교 대상인 child를 설정했으니 루트노드에 위치 중인 temp와 비교한다.
		// temp가 더 작다면 위치이동을 할 필요가 없으므로 이 반복문을 빠져나간다.
		// 제자리에 있다는 뜻이다. 최소히프는 작은 값이 부모로 있어야 한다.
		if (temp.key <= h->heap[child].key)
			break;

		// 여기까지 왔다는 건 temp의 자리교환이 필요하다는 뜻이다.
		// temp가 있을 곳을 찾기 위해 비교대상을 한 단계 아래로 이동한다.
		h->heap[parent] = h->heap[child]; // 자녀의 값이 새로운 비교 기준점이 된다.
		parent = child; // 자녀가 부모로 된다. (다음 비교를 위해)
		child *= 2; // 2를 곱하여 다음 자녀로 된다.
	}
	// 위 반복문을 빠져나오면, parent가 temp가 위치할 곳이 되어 있을 것이다.
	h->heap[parent] = temp;
	return item;
}

void insert_heap_edge(HeapType *h, int u, int v, int weight)
{
	element e;
	e.u = u;
	e.v = v;
	e.key = weight;
	insert_min_heap(h, e);
}

void insert_all_edges(HeapType *h) // 직접 그림을 그려보면 편하다.
{
	// 최소히프이므로 가장 작은 노드가 루트노드로 위치하게 된다.
	insert_heap_edge(h, 0, 1, 29);
	insert_heap_edge(h, 1, 2, 16);
	insert_heap_edge(h, 2, 3, 12);
	insert_heap_edge(h, 3, 4, 22);
	insert_heap_edge(h, 4, 5, 27);
	insert_heap_edge(h, 5, 0, 10);
	insert_heap_edge(h, 6, 1, 15);
	insert_heap_edge(h, 6, 3, 18);
	insert_heap_edge(h, 6, 4, 25);
}

// kruskal의 최소 비용 신장 트리 알고리즘
void kruskal(int n)
{
	int edge_accepted = 0;	// 현재까지 선택된 간선의 수
	HeapType h;				// 최소 히프
	int uset, vset;			// 정점 u와 정점 v의 집합 번호
	element e;				// 히프 요소

	init(&h);				// 히프 초기화
	insert_all_edges(&h);	// 히프에 간선들을 삽입
	set_init(n);			// 집합 초기화
	
	while (edge_accepted < (n - 1)) // 간선의 수 < (n - 1)
	{
		e = delete_min_heap(&h);	// 가장 작은 가중치의 간선 획득
		// 획득됨과 동시에 해당 간선은 히프에서 제거된다.
		uset = set_find(e.u);		// 정점 u의 집합 번호
		vset = set_find(e.v);		// 정점 v의 집합 번호

		// 두 집합이 서로 다른 집합에 속한다면
		if (uset != vset)
		{
			printf("(%d, %d) %d \n", e.u, e.v, e.key);
			edge_accepted++;
			set_union(uset, vset);	// 두 개의 집합을 합친다.
		}
	}
}

void main()
{
	kruskal(7);
}
/*************************************************
 ** End Line
*************************************************/