신장 트리(Spanning Tree)는 그래프의 모든 정점을 연결하는, 연결된 무방향 그래프의 부분 그래프입니다. 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있으며, 그중 최소 신장 트리(MST, Minimum Spanning Tree)는 다른 모든 신장 트리와 비교해 같거나 더 작은 가중치의 합을 가집니다. 각 간선에는 가중치가 할당되고, 그 합이 해당 신장 트리의 총 가중치가 됩니다. 그래프의 정점 수를 V라고 할 때, 최소 신장 트리는 항상 (V − 1)개의 간선으로 구성됩니다.
크루스칼(Kruskal) 알고리즘으로 최소 신장 트리 찾기
- 그래프의 모든 간선을 가중치 기준 오름차순(비내림차순)으로 정렬합니다.
- 가중치가 가장 작은 간선부터 차례로 선택하되, 사이클이 형성되지 않는 경우에만 결과에 포함합니다.
- 신장 트리가 (V − 1)개의 간선을 가질 때까지 위 과정을 반복합니다.
여기서 사용하는 것이 바로 탐욕(Greedy) 기법입니다. 탐욕적 선택이란 매 순간 가중치가 가장 작은 간선을 선택하는 전략을 의미합니다. 예를 들어 아래 그래프의 최소 신장 트리는 (9 − 1) = 8개의 간선으로 구성됩니다.
1단계: 간선 정렬
정렬 후: 가중치 시작 도착 21 27 26 22 28 22 22 26 25 24 20 21 24 22 25 26 28 26 27 22 23 27 27 28 28 20 27 28 21 22 29 23 24 30 25 24 31 21 27 34 23 25
2단계: 정렬된 순서대로 간선 선택
이제 정렬된 순서대로 간선을 하나씩 검사합니다.
- 간선 26–27 → 사이클이 형성되지 않으므로 포함
- 간선 28–22 → 사이클이 형성되지 않으므로 포함
- 간선 26–25 → 사이클이 형성되지 않으므로 포함
- 간선 20–21 → 사이클이 형성되지 않으므로 포함
- 간선 22–25 → 사이클이 형성되지 않으므로 포함
- 간선 28–26 → 사이클이 형성되므로 제외
- 간선 22–23 → 사이클이 형성되지 않으므로 포함
- 간선 27–28 → 사이클이 형성되므로 제외
- 간선 20–27 → 사이클이 형성되지 않으므로 포함
- 간선 21–22 → 사이클이 형성되므로 제외
- 간선 23–24 → 사이클이 형성되지 않으므로 포함
선택된 간선 수가 (V − 1)개에 도달했으므로 여기서 알고리즘이 종료됩니다.
C++ 구현 예제
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E){
struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E);
return graph;
}
struct subset {
int parent;
int rank;
};
int find(struct subset subsets[], int i){
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y){
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int myComp(const void* a, const void* b){
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph){
int V = graph->V;
struct Edge
result[V];
int e = 0;
int i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
struct subset* subsets
= (struct subset*)malloc(V * sizeof(struct subset));
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1 && i < graph->E) {
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Following are the edges in the constructed MST\n");
int minimumCost = 0;
for (i = 0; i < e; ++i){
printf("%d -- %d == %d\n", result[i].src,
result[i].dest, result[i].weight);
minimumCost += result[i].weight;
}
printf("Minimum Cost Spanning tree : %d",minimumCost);
return;
}
int main(){
/* Let us create the following weighted graph
30
0--------1
| \ |
26| 25\ |15
| \ |
22--------23
24 */
int V = 24;
int E = 25;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 20;
graph->edge[0].dest = 21;
graph->edge[0].weight = 30;
graph->edge[1].src = 20;
graph->edge[1].dest = 22;
graph->edge[1].weight = 26;
graph->edge[2].src = 20;
graph->edge[2].dest = 23;
graph->edge[2].weight = 25;
graph->edge[3].src = 21;
graph->edge[3].dest = 23;
graph->edge[3].weight = 35;
graph->edge[4].src = 22;
graph->edge[4].dest = 23;
graph->edge[4].weight = 24;
KruskalMST(graph);
return 0;
}
실행 결과
Following are the edges in the constructed MST 22 -- 23 == 24 20 -- 23 == 25 20 -- 21 == 30 Minimum Cost Spanning tree : 79
마무리
이번 글에서는 탐욕 기법에 기반한 크루스칼 최소 신장 트리 알고리즘의 개념과 이를 C++로 구현하는 방법을 살펴보았습니다. 동일한 로직은 Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 크루스칼의 아이디어를 그대로 모델링한 이 프로그램은 주어진 그래프에서 최소 비용 신장 트리를 효율적으로 찾아냅니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.