[알고리즘] 크루스칼(Kruskal)

1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다.

2. 정렬된 간선들을 차례대로 채택하여 그래프를 만들어간다.

3. 사이클이 형성될 경우 그 간선은 채택되지 않는다.

   *사이클 체크는 유니온 파인드(Union-Find)로

4. 이 과정을 반복하면, 최소 스패닝 트리가 된다.

 

정점의 개수 V, 간선의 개수 E 일때,

시간 복잡도는 유니온 파인드에서 O(V)라고 해도, 간선을 정렬할 때 이미 O(ElogE)이기 때문에

크루스칼의 시간 복잡도는 보통 O(ElogE)라 한다

총 가중치 합이 46인 스패닝 트리가 만들어진다.

 

 

코드(c++)

#include<bits/stdc++.h>
using namespace std;
#define Pair pair<int,pair<int,int>>
vector<int> parent;
vector<Pair> graph;
int n;

// 사이클 체크 함수 (Union_Find)
int Find(int v){ 
    if(parent[v] != v) parent[v] = Find(parent[v]);
    return parent[v];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    // parent vector 초기화
    parent.resize(n+1);
    for(int i=0; i<=n; i++) parent[i] = i;
    // graph input
    for(int i=0; i<n; i++){
        int a,b,v;
        cin>>a>>b>>v;
        graph.push_back({v,{a,b}});
    }
    int answer=0;
    // 크루스칼
    sort(graph.begin(), graph.end());
    for(int i=0; i<graph.size(); i++){
        int node1 = graph[i].second.first,
            node2 = graph[i].second.second;
        // 사이클 체크
        int parentA = Find(node1);
        int parentB = Find(node2);
        if(parentA != parentB){ // 사이클이 생기지 않으면
            parent[parentA] = parentB;
            answer += graph[i].first;
        }
    }
    cout << answer;
    return 0;
}

input

8
1 2 9
1 3 7
2 3 5
3 4 13
2 5 17
4 5 11
5 7 7
5 6 3

 

output

46

 

 

*방향이 있는 그래프에서는 directed mst라고 고급 알고리즘이 따로 있다.

사이클을 발견하면 트리 압축을 하면서... 뭐 그냥 그런게 있다.

대표적인 예제로는 미생물 키우기

https://www.acmicpc.net/problem/16127