- 먼저, 간선들의 가중치를 오름차순으로 정렬한다.
- 가중치가 작은 간선부터 사이클을 형성하는지 검사한다. (유니온-파인드: 두 개의 노드가 같은 집합에 포함되는지 검사)
- 사이클을 형성하지 않는 간선만 포함시킨다.
#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;
}
입력: 가중치 그래프 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)로 줄일 수 있다.
크루스칼 알고리즘은 간선들의 가중치를 오름차순으로 정렬한 뒤 사이클을 형성하지 않는 간선들만 MST에 차례로 추가하였다. 반면에, 프림 알고리즘은 MST에 속하지 않은 정점들 중에서 가중치가 가장 작은 정점들을 하나씩 추가하였다.
즉, 크루스칼 알고리즘은 사이클 없이 '간선'을 하나씩 추가하는 방식이라면, 프림 알고리즘은 MST에 속하지 않은 '정점'들을 하나씩 추가하는 방식이다.
다른 관점에서 보자면, 크루스칼은 n개의 트리들이 점차 합쳐져서 1개의 신장 트리를 만드는 반면에, 프림은 1개의 트리가 자라나서 최종적인 신장 트리가 된다고 볼 수 있다.