[알고리즘] 최소 신장 트리를 위한 Disjoint set과 크루스칼 알고리즘

 최소 신장 트리(MST, Minimum Spanning Tree)란?

 - 가중치가 있는 무향 그래프가 주어졌을 때 모든 노드를 연결하면서 간선의 가중치 합이 최소인 신장 트리를 뜻한다.

 

최소 신장 트리의 특징

 1) 가중치의 합이 최소

 2) N개의 노드에 대하여 N-1개의 간선으로 구성

 3) 사이클이 존재하지 않아야 함

 

최소 신장 트리를 구하는 방법

 그래프가 주어졌을 때 우리는 어떻게 최소 신장 트리를 찾을 수 있을까? 간단한 방법으로 가중치가 작은 간선을 선택할 수 있는지 확인하여 포함하는 Greedy 방식으로 MST를 구할 수 있다.

 * 가중치가 작은 순서대로 간선을 탐색하면서 Spanning Tree의 조건에 부합하는 간선만 선택

 * 간선을 선택시에 사이클이 있는지 여부를 판단해서 해당 간선을 연결할지 않을지 결정 

 * 사이클 여부는 disjoint set을 이용하여, 해당 노드의 공통 조상이 다른지 여부를 확인하면 쉽게 알 수 있다.

 

 

Disjoint set 알고리즘 + Kruskal MST 알고리즘 

본 소스코드는 백준 최소 스패닝 트리에 기반을 두고 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> piii;
#define fff first.first
#define sss first.second
#define ttt second
#define mp(x, y) make_pair((x), (y))
#define mpp(x, y, z) mp(mp((x), (y)), (z))


int V, E;
vector<piii> edge;
int p[10005];

int par(int x){
    if(x==p[x]) return x;
    p[x] = par(p[x]);
    return p[x];
}
int merge(int x, int y){
    x = par(x);
    y = par(y);
    if(x!=y){
        p[y] = x;
        return 1;
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E;
    int a, b, c;
    for(int i = 1; i <= V; i++){
        p[i] = i;
    }
    for(int i = 0; i < E; i++){
        cin >> a >> b >> c;
        edge.push_back(mpp(c, a, b));
    }
    sort(edge.begin(), edge.end());
    long long res = 0;
    for(int i = 0; i < edge.size(); i++){
        if(merge(edge[i].sss, edge[i].ttt))
            res+=edge[i].fff;
    }
    cout << res << endl;

}

 

크루스칼 알고리즘은 간선을 필요로 한다. 간선의 경우 양쪽 노드와 가중치를 가지고 있으므로, 이 데이터를 저장하기 위하여 pair를 두번 겹쳐서 pair<pair<int, int> int>을 이용한다.

 이후 크루스칼 알고리즘을 위하여 간선을 가중치가 적은 순으로 정렬해야 하는데, algorithm의 sort 함수를 이용하면, pair의 first, second의 오름차순으로 정렬이 진행된다.

 이때 해당 간선을 선택할지 않을지는 union find 구조의 disjoint set으로 확인한다. 만약 두개의 공통 조상의 값이 다르다면 두 노드는 상호 베타 집합에 있었으므로 연결되어도 사이클을 생성하지 않는다. 즉, 상호 베타 집합인 경우만 간선의 가중치를 더함으로써 우리는 MST의 가중치 합을 구할 수 있다.

 

 disjoint set은 소스코드의 merge와 par 함수를 통해서 쉽게 정의할 수 있다. 전체적인 방향은 1) 자신의 부모를 저장하는 배열 선언, 2) 자신의 부모를 찾는 함수 작성(par) , 3) 두 노드의 부모가 최상위 공통 부모가 다르면, 두 노드를 합치고 다시 저장 (merge)

 이때 부모를 찾는 함수를 호출만 하게되는 경우 간선의 개수*2번 만큼 최악의 경우 N번의 탐색이 발생할 수 있다. 따라서 우리는 경로 압축을 이용한다.  p[x] = par(par[x])

 추가적으로 merge에서 두 노드 x, y중 x를 y의 부모로 하든지 반대로 y를 x의 부모로 하든지 상관없다.