그래프 - Kruskal의 MST 알고리즘

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

 

Kruskal의 MST 알고리즘

 

이 알고리즘은 탐욕적인 방법을 사용해 최소 비용 신장 트리를 알아낸다.

 

탐욕적인 방법이란, 선택할 때마다 그 순간에 가장 좋다고 판단되는 것을 선택하는 방법이다.

*탐욕적인 방법 = 그리디 알고리즘 = greedy method 

 

하지만, 항상 최적의 결론을 내리는가에 대한 검증이 필요한데, 

크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명이 되어 있어서 이 부분은 신경쓰지 않아도 된다.

 

크루스칼 알고리즘을 사용하는 이유는 최소 비용 신장 트리(MST)를 알아내기 위함이다.

 

최소비용신장트리가 되기 위해 필수적으로 만족해야 하는 조건 3가지를 보면,

 

1. 간선의 가중치의 합이 최소
2. 모든 정점 n개에 대해, 간선 (n-1)개만 사용
3. 사이클 미 포함

 

그렇다면, 어떻게 구할 수 있을까?

 

크루스칼 알고리즘을 사용해 최소비용신장트리를 구하는 순서는 다음과 같다.

 

1. 그래프의 모든 간선들을 오름차순(↗)으로 정렬한다.
2. 아직 사용하지 않은 간선 중, 가중치가 가장 작은 간선을 선택한다.
3. 이미 선택된(최소비용신장트리에 담긴) 간선들과 사이클을 형성하지 않는다면, 최소비용신장트리에 추가한다.
4. 사이클을 형성한다면, 그 간선은 제외하고 그 다음으로 가중치가 큰 간선에 대해 위의 과정을 반복한다.

 

위의 순서를 보면

정렬해서 가장 작은 가중치를 갖는 간선을 찾는 것은 구현하는 것은 쉽지만,

사이클 형성 여부를 확인하는 것은 어떻게 구현해야 할지 고민이 된다.

 

사이클이 무엇인가?

트리의 시작 정점과 도착 정점이 같아 돌고 도는 경우를 의미한다.

 

사이클 형성 여부를 판단하기 위해서는 

추가하고자 하는 간선의 양 끝 정점이 같은 집합에 속해 있는지 검사하면 된다.

 

이는 union-find 연산으로 구현되어 있다. 

union-find 연산

# union 연산: union(x,y) 

원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합을 합집합을 만든다.

 

이때 두 집합(트리)의 루트 노드 중

원소 x가 속한 집합(트리)의 루트노드가 새로운 합집합의 루트노드가 된다.

# find 연산: find(x)

원소 x가 속해있는 집합의 루트 노드를 반환한다.

 

그림으로 이해하기

다음 그래프에 대한 최소비용신장트리를 구해보자.

우선, 간선들을 오름차순으로 정렬하면 다음과 같다.

가중치가 작은 순서대로 union-find 연산을 통해 사이클을 형성하는지 확인하고, 

안한다면 최소비용신장트리에 추가하자.

 

물론, 맨 처음에는 최소비용신장트리는 공집합 {} 이다.

 

#1. 정점들을 모두 하나씩 분리해 독자적인 집합으로 만들자.

#2. 정렬된 간선 리스트에서 가중치가 작은 순서대로 union-find 연산을 진행한다.

 

단, find 연산에서 각 정점이 포함된

두 집합의 루트 노드가 다르면 해당 간선은 포함되고, 

두 집합의 루트 노드가 같으면 해당 간선은 포함되지 않음을 유의하면서 따라가자.

 

• 간선 (0,5) (2,3) (1,6) 까지 union-find 연산을 진행하면 다음과 같다.

그림1

• 간선 (1,2) 에 대해 union-find 연산을 수행하자.

그림2

여기까지는, find 연산을 통해 간선 (x,y)의 정점x의 루트노드와 정점y의 루트노드가 다르므로

사이클이 형성되지 않기 때문에 간선 (0,5) (2,3) (1,6) (1,2) 는 모두 최소비용신장트리에 포함된다.

 

• 간선 (3,6) 에 대해 union-find 연산을 수행하자.

그림2를 보니, 간선 (3,6)의 양 끝 정점 3과 6의 루트노드가 모두 1로 동일하다.

즉, 1->2->3->6->1 로 사이클이 형성됨을 알 수 있고,

이는 최소비용신장트리의 조건을 만족하지 않기 때문에 제외해야 한다.

 

• 간선 (3,4) 에 대해 union-find 연산을 수행하자.

정점3과 4의 루트노드가 다르므로 사이클이 형성되지 않고, 최소비용신장트리에 포함된다.

그림3

• 간선 (4,6) 에 대해 union-find 연산을 수행하자.

정점 4와 6의 루트 노드가 모두 1로 동일하므로 사이클이 형성되기 때문에 제외한다.

 

• 간선 (4,5) 에 대해 union-find 연산을 수행하자.

정점 5와 4의 루트 노드가 각각 0과 1로 다름을 그림3을 통해 알 수 있다.

이 간선은 최소비용신장트리에 추가된다.

그림4

• 간선 (0,1) 은 사이클을 형성하므로 제외한다.

 

결국, 최소 비용 신장트리는 다음의 간선들을 포함하고,

결론적으로는, 다음과 같이 최소비용신장트리가 완성된다.

 

c언어로 구현

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 100
/******************* Union-Find 연산 **********************/
int parent[MAX_VERTICES];	// 루트 노드를 저장하는 배열

void set_init(int n)		// 집합의 원소를 하나씩 분리: {1} {2} ...
{
	for (int i = 0; i < n; i++)
		parent[i] = -1;
}
// 정점 curr가 속하는 지밥의 루트 노드를 반환한다.
int set_find(int curr)
{
	if (parent[curr] == -1)		// 단일 노드인 경우임: 루트가 자기자신일 때
		return curr;
	while (parent[curr] != -1)	// 루트 노드를 찾아 떠남
		curr = parent[curr];
	return curr;
}
// union: 두 개의 정점이 속한 트리/집합을 합치기
void set_union(int a, int b)
{
	int root1 = set_find(a);
	int root2 = set_find(b);

	if (root1 != root2) {
		parent[root2] = root1;
	}
}
/************************* Graph *******************************/
struct Edge {
	int start, end, weight; 
};
typedef struct GraphType
{
	int n;			// 정점의 개수
	struct Edge edges[2 * MAX_VERTICES];
} GraphType;
// 그래프 초기화
void graph_init(GraphType* g)
{
	g->n = 0;
	for (int i = 0; i < 2 * MAX_VERTICES; i++)
	{
		g->edges[i].start = 0;
		g->edges[i].end = 0;
		g->edges[i].weight = INF;
	}
}
// 간선 삽입
void insert_edge(GraphType* g, int start, int end, int weight)
{
	g->edges[g->n].start = start;
	g->edges[g->n].end = end;
	g->edges[g->n].weight = weight;
	g->n++;
}
// qsort()에 사용되는 함수
int compare(const void* a, const void* b)	// 가중치 정렬할 때 사용할 함수
{
	struct Edge* x = (struct Edge*)a;
	struct Edge* y = (struct Edge*)b;
	return (x->weight - y->weight);
}
/*************************** Kruskal **********************************/
// kruskal 함수
void kruskal(GraphType* g)
{
	int edge_accepted = 0;		// 현재까지 선택된 간선의 개수
	int uset, vset;				// 정점 u와 정점 v의 집합 번호
	struct Edge e;

	set_init(g->n);				// 현존하는 간선에 대해, 루트 노드 모두 -1로 초기화
	qsort(g->edges, g->n, sizeof(struct Edge), compare);

	printf("크루스칼 최소 신장 트리 알고리즘\n");
	int i = 0;
	while (edge_accepted < (g->n - 1))	// 간선의 개수 < (n-1)
	{
		e = g->edges[i];		// e <- (start, end, weight)
		uset = set_find(e.start);	// 간선 e의 시작 정점의 루트노드
		vset = set_find(e.end);		// 간선 e의 끝 정점의 루트노드

		if (uset != vset)
		{
			printf("간선 (%d, %d) %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++;
			set_union(uset, vset);	// 두 개의 집합 합치기
		}
		i++;
	}
}
int main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	if (g == NULL) {
		printf("그래프 할당 오류\n");
		return -1;
	}
	graph_init(g);

	insert_edge(g, 0, 1, 29);
	insert_edge(g, 1, 2, 16);
	insert_edge(g, 2, 3, 12);
	insert_edge(g, 3, 4, 22);
	insert_edge(g, 4, 5, 27);
	insert_edge(g, 5, 0, 10);
	insert_edge(g, 6, 1, 15);
	insert_edge(g, 6, 3, 18);
	insert_edge(g, 6, 4, 25);

	kruskal(g);
	free(g);
	return 0;
}

*qsort()

qsort(정렬할배열/메모리주소, 요소개수, 요소크기, 비교함수);

결과

 

시간복잡도

Kruskal 알고리즘은 간선들을 정렬하는 시간에 좌우된다.

따라서 간선의 개수를 e라고 하면, 시간 복잡도는 O(eloge) 이다.