최소 신장 트리 (Minimum Spanning Tree, MST)
- 신장 트리: 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리
- 최소 신장 트리: 간선들의 가중치 합이 최소가 되는 신장 트리
- 각 도시를 정점, 도로를 간선, 도시 간의 거리를 가중치라고 하면, 최소 신장 트리는 모든 도시들을 사이클 없이 연결하면서도 그 거리의 합이 최소가 되는 도로망을 의미한다.
- 정점 개수가 n개일 때, 사이클 없이 모든 정점을 연결하면 간선의 개수는 항상 (n-1)개가 된다.
- 최소 신장 트리를 구하는 대표적인 방법으로 크루스칼, 프림 알고리즘이 있다.
- 크루스칼 알고리즘은 가중치가 최소인 간선부터, 프림 알고리즘은 가중치가 최소인 정점부터 하나씩 MST에 포함시킨다는 점에서 둘다 그리디 알고리즘으로 분류할 수 있다.
크루스칼 알고리즘
알고리즘 이해
- 먼저, 간선들의 가중치를 오름차순으로 정렬한다.
- 가중치가 작은 간선부터 사이클을 형성하는지 검사한다. (유니온-파인드: 두 개의 노드가 같은 집합에 포함되는지 검사)
- 사이클을 형성하지 않는 간선만 포함시킨다.
코드로 구현 (C++)
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int v, e; // 노드와 간선의 개수 (최대 10만개)
int parent[100001]; // 부모 테이블 초기화
vector<pair<int, pair<int, int>>> edges; // 모든 간선을 담을 배열
int result = 0;
// 특정 원소가 속한 집합 찾아내기
int findParent(int x){
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b){
a = findParent(a);
b = findParent(b);
// 더 작은 번호가 부모 노드가 되도록
if(a < b) parent[b] = a;
else parent[a] = b;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> v >> e;
// 부모 테이블 초기화
for(int i = 1; i <= v; i++){
parent[i] = i;
}
// 모든 간선에 대한 정보 입력 받기
for(int i = 0; i < e; i++){
int a, b, cost;
cin >> a >> b >> cost;
edges.push_back({cost, {a, b}});
}
// 간선을 비용 순으로 정렬
sort(edges.begin(), edges.end());
// 간선을 하나씩 확인하면서
for(int i = 0; i < edges.size(); i++){
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
// 사이클이 발생하지 않는 경우에만 MST에 포함시키기
if(findParent(a) != findParent(b)){
unionParent(a, b);
result += cost;
}
}
cout << result;
return 0;
}시간복잡도 분석
- 크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간복잡도를 갖는다.
- 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선의 정렬을 수행하는 부분이다. 표준 라이브러리를 이용해 E개의 데이터를 정렬하기 위한 시간복잡도는 O(ElogE)이다.
프림 알고리즘
의사 코드
입력: 가중치 그래프 G=(V, E), |V|=n (정점 개수), |E|=m (간선 개수)
출력: 최소 신장 트리
1. 그래프 G에서 임의의 점 p를 시작점으로 선택, D[p]=0
// D[v]: T에 있는 점 u와 그 밖에 있는 점 v를 연결하는 간선 중에서 최소 가중치를 저장하는 배열
2. for(점 p가 아닌 각 점 v에 대해서){
3. if(그래프 상에 간선 (p, v)가 있으면)
4. D[v] = 간선 (p, v)의 가중치
5. else
6. D[v] = ∞
}
7. T = {p} // 임의의 점 p부터 시작
8. while(T에 있는 점의 수 < n) {
9. T에 속하지 않은 각 점 v에 대해서, D[v]가 최소인 점 v_min을 찾아 T에 추가
10. for(T에 속하지 않은 각 점 w에 대해서) {
11. if(간선 (v_min, w)의 가중치 < D[w])
12. D[w] = 간선 (v_min, w)의 가중치 // D[w] 갱신
}
}
13. return T // 최소 신장 트리 T 리턴알고리즘 이해
시간복잡도 분석
8. while(T에 있는 점의 수 < n) {
9. T에 속하지 않은 각 점 v에 대해서, D[v]가 최소인 점 v_min을 찾아 T에 추가
10. for(T에 속하지 않은 각 점 w에 대해서) {
11. if(간선 (v_min, w)의 가중치 < D[w])
12. D[w] = 간선 (v_min, w)의 가중치 // D[w] 갱신
}
}총 n개의 노드들은 매번 가중치가 최소인 점 v_min을 D[v] 배열에서 선형 탐색으로 찾아야 하므로 시간복잡도는 O(n^2)이다.
최단 경로 알고리즘과 마찬가지로, 현재 노드로부터의 거리가 최소가 되는 v_min을 찾기 위해서 배열 대신에 최소 힙 자료구조를 사용하면, 시간복잡도를 O(ElogV)로 줄일 수 있다.
크루스칼 vs. 프림 알고리즘
크루스칼 알고리즘은 간선들의 가중치를 오름차순으로 정렬한 뒤 사이클을 형성하지 않는 간선들만 MST에 차례로 추가하였다. 반면에, 프림 알고리즘은 MST에 속하지 않은 정점들 중에서 가중치가 가장 작은 정점들을 하나씩 추가하였다.
즉, 크루스칼 알고리즘은 사이클 없이 '간선'을 하나씩 추가하는 방식이라면, 프림 알고리즘은 MST에 속하지 않은 '정점'들을 하나씩 추가하는 방식이다.
다른 관점에서 보자면, 크루스칼은 n개의 트리들이 점차 합쳐져서 1개의 신장 트리를 만드는 반면에, 프림은 1개의 트리가 자라나서 최종적인 신장 트리가 된다고 볼 수 있다.
꾸준히!