[자료구조] 크루스칼(Kruskal)의 MST 알고리즘

 

크루스칼(Kruskal)의 MST 알고리즘

Kruskal 알고리즘은 탐욕적인 방법(Greedy, 그리디)를 사용합니다.

그리디를 간략하게 설명하자면, 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법입니다. 그리디는 근사적인 방법이기 때문에 항상 최적의 해답을 주지 않을 수도 있습니다. 하지만 Kruskal의 MST 알고리즘은 최적의 해답을 주는 것으로 증명되었기 때문에 이 방법으로 최적해(최단 경로)를 구할 수 있습니다.

알고리즘의 작동 방식은 다음과 같습니다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬함
2. 사이클을 형성하지 않는 간선을 찾아서 최소 신장 트리의 집합에 추가함
   • 가장 낮은 가중치를 가진 간선을 먼저 선택함
   • 만약 사이클을 형성하는 간선이 있다면 그 간선은 제외함
3. 선택된 간선을 최소 신장 트리에 추가함

 

최소 신장 트리 구하는 과정

예시로 한 그래프에서 Kruskal 알고리즘을 이용해 MST를 구해보도록 하겠습니다.

 

우선 그래프의 간선들을 가중치의 오름차순으로 정렬해보겠습니다. (공간 상 나머지는 생략하겠습니다.)

vertex	3-7	0-4	4-5	0-5	1-3	1-4	1-5	2-6	2-4
edge	4	7	7	8	8	9	11	15	16

 

Kruskal 알고리즘의 과정을 차례대로 따라가보면 n개의 정점과 n-1개의 간선으로 이루어짐을 알 수 있습니다.

결론적으로 이 그래프의 최소 신장 트리는 마지막 사진에 색칠한 것과 같이 이루어짐을 알 수 있습니다.

 

코드로 구현하면 아래와 같습니다.

int parent[MAX_VERTICES]; // 부모 노드

void set_init(int n) {
    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;
}

// 두 개의 원소가 속한 집합을 합침
void set_union(int a, int b) {
    int root1 = set_find(a); // 노드 a의 루트를 찾는다.
    int root2 = set_find(b); // 노드 b의 루트를 찾는다.
    if(root1 != root2) { // 합한다.
        parent[root1] = root2;
    }
}

struct Edge { // 간선을 나타내는 구조체
	int start, end, weight;
};

typedef struct Graph {
	int n;
	int nvertex;
	struct Edge edges[2 * MAX_VERTICES];
} Graph;

// 그래프 초기화
void graph_init(Graph *g) {
	g->n = g->vertex = 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(Graph *g, int start, int end, int w) {
	g->edges[g->n].start = start;
	g->edges[g->n].end = end;
	g->edges[g->n].weight = w;
	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);
}

void kruskal(Graph *g) {
	int edge_accepted = 0; // 현재까지 선택된 간선의 수
	int uset, vset; // 정점 u와 정점 v의 집합 번호
	struct Edge e;

	set_init(g->nvertex); // 집합 초기화
	qsort(g->edges, g->n, sizeof(struct Edge), compare);

	printf(“크루스칼 최소 신장 트리 알고리즘 \n”);
	int i = 0;
	while(edge_accpted < (g->nvertex - 1)) { // 간선의 수 < (n - 1)
		e = g->edges[i];
		uset = set_find(e.start); // 정점 u의 집합 번호
		vset = set_find(e.end); // 정점 v의 집합 번호
		if(uset != vset) { // 서로 속한 집합이 다르면
			printf("간선 (“%d, %d) %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++;
			set_union(uset, vset); // 두 개의 집합을 합친다.
		}
		i++;
	}
}