개요
이 튜토리얼에서는 C++의 STL(표준 템플릿 라이브러리)을 활용하여 크루스칼(Kruskal) 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘을 구현하는 방법을 살펴봅니다.
크루스칼 알고리즘은 연결된 무방향 가중치 그래프가 주어졌을 때, 모든 정점을 연결하면서 간선 가중치의 총합이 최소가 되는 신장 트리를 찾는 대표적인 그리디(Greedy) 알고리즘입니다.
알고리즘 동작 원리
크루스칼 알고리즘은 다음 순서로 진행됩니다.
- 그래프의 모든 간선을 가중치 기준 오름차순으로 정렬합니다.
- 가중치가 가장 작은 간선부터 차례대로 검사하며, 선택 시 사이클이 발생하지 않는 경우에만 트리에 추가합니다.
- 사이클 생성 여부는 서로소 집합(Disjoint Set, Union-Find) 자료구조를 통해 효율적으로 판별합니다.
- (정점 수 − 1)개의 간선이 모두 선택되면 알고리즘이 종료됩니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> iPair;
// 그래프 구조체
struct Graph{
int V, E;
vector< pair<int, iPair> > edges;
Graph(int V, int E){
this->V = V;
this->E = E;
}
void addEdge(int u, int v, int w){
edges.push_back({w, {u, v}});
}
int kruskalMST();
};
// 서로소 집합(Union-Find) 구조체
struct DisjointSets{
int *parent, *rnk;
int n;
DisjointSets(int n){
this->n = n;
parent = new int[n+1];
rnk = new int[n+1];
for (int i = 0; i <= n; i++){
rnk[i] = 0;
parent[i] = i;
}
}
int find(int u){
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void merge(int x, int y){
x = find(x), y = find(y);
if (rnk[x] > rnk[y])
parent[y] = x;
else
parent[x] = y;
if (rnk[x] == rnk[y])
rnk[y]++;
}
};
int Graph::kruskalMST(){
int mst_wt = 0;
// 간선을 가중치 기준으로 정렬
sort(edges.begin(), edges.end());
DisjointSets ds(V);
vector< pair<int, iPair> >::iterator it;
for (it=edges.begin(); it!=edges.end(); it++){
int u = it->second.first;
int v = it->second.second;
int set_u = ds.find(u);
int set_v = ds.find(v);
// 사이클을 만들지 않는 경우에만 선택
if (set_u != set_v){
cout << u << " - " << v << endl;
mst_wt += it->first;
ds.merge(set_u, set_v);
}
}
return mst_wt;
}
int main(){
int V = 9, E = 14;
Graph g(V, E);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
cout << "Edges of MST are \n";
int mst_wt = g.kruskalMST();
cout << "\nWeight of MST is " << mst_wt;
return 0;
}
실행 결과
Edges of MST are
6 - 7
2 - 8
5 - 6
0 - 1
2 - 5
2 - 3
0 - 7
3 - 4
Weight of MST is 37
코드 핵심 요소 분석
1. Graph 구조체
간선을 {가중치, {정점 u, 정점 v}} 형태의 pair로 저장합니다. 가중치를 pair의 첫 번째 요소에 배치하면 sort() 호출만으로 가중치 오름차순 정렬이 자동으로 이루어집니다.
2. DisjointSets(Union-Find) 구조체
- find(): 특정 정점이 속한 집합의 루트를 찾습니다. 경로 압축(Path Compression)을 적용해 탐색 속도를 높였습니다.
- merge(): 두 집합을 하나로 합칩니다. 랭크(Rank) 기반 합병을 사용해 트리의 균형을 유지합니다.
3. kruskalMST() 함수
정렬된 간선을 순회하며 두 정점이 서로 다른 집합에 속해 있는지 확인합니다. 같은 집합이라면 간선 추가 시 사이클이 생기므로 건너뛰고, 다른 집합이라면 간선을 선택하고 두 집합을 병합합니다.
시간 복잡도
크루스칼 알고리즘의 전체 시간 복잡도는 간선 정렬이 지배적이며, O(E log E)입니다. 여기서 E는 간선의 개수입니다. Union-Find 연산 자체는 거의 상수 시간에 처리되므로 전체 성능에 큰 영향을 주지 않습니다.