126. Kruskal's Algorithm

크루스칼 알고리즘(Kruskal's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 알고리즘 중 하나로, 다음과 같은 방법으로 작동한다.

    1. 확인하지 않은 간선들 중 가중치가 가장 작은 간선 하나를 고른다.

    2. 현재까지의 최소 스패닝 트리에서 선택한 간선이 연결하는 두 정점이 연결되어 있지 않다면, 이 간선을 최소 스패닝 트리에 추가한다.

    3. 모든 간선을 확인했다면 종료한다. 그렇지 않다면 1번으로 돌아간다.

 

설명이 매우 간단하게 끝난다. 예시를 통해서 자세히 살펴보자.

앞에서 나온 그래프이다. 여기서 가중치가 작은 간선들부터 하나씩 확인하면서 최소 스패닝 트리를 만든다. 먼저 가중치가 $2$인 간선들이 최소 스패닝 트리에 추가된다.

다음으로 가중치가 $3$인 간선을 확인하는데, 정점 $\text{A}$와 $\text{F}$가 이미 다른 간선들로 연결되어 있으므로 이 간선을 최소 스패닝 트리에 추가하지 않는다. 다음으로 가중치가 $4$인 간선들을 확인한다. 이 간선들은 전부 최소 스패닝 트리에 추가된다.

다음으로 가중치가 $5$인 간선들이 최소 스패닝 트리에 추가된다.

가중치가 $6$인 간선, 가중치가 $7$인 간선은 최소 스패닝 트리에 추가되지 않는다. 다음으로 가중치가 $8$인 간선들을 확인하는데, 둘 중 어떤 간선을 먼저 확인하던간에 그 간선을 최소 스패닝 트리에 추가하면 다른 간선은 최소 스패닝 트리에 추가되지 않는다. 여기서는 정점 $\text{B}$와 $\text{C}$를 연결하는 간선이 추가되었다고 가정한다.

가중치가 $9$인 간선은 최소 스패닝 트리에 추가되지 않는다. 남은 간선이 없으므로 여기서 추가된 간선들이 최소 스패닝 트리를 구성하게 된다.

---

크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 과정에서, 같은 가중치의 간선들을 확인할 때 최소 스패닝 트리에 추가되는 간선의 개수는 어떤 간선을 선택하는지에 상관없이 동일하다. 이는 선택하는 간선에 상관없이 컴포넌트의 개수가 동일하게 줄어들기 때문이다. 따라서 최소 스패닝 트리를 구성하는 간선들의 가중치를 정렬하면 항상 같은 결과가 나오게 된다. 위 그래프의 경우 최소 스패닝 트리를 구성하는 간선들의 가중치를 정렬하면 항상 $2$, $2$, $2$, $4$, $4$, $5$, $5$, $8$이 나온다.

 

다음으로 이 알고리즘의 정당성을 보인다.

크루스칼 알고리즘으로 찾은 스패닝 트리가 최소 스패닝 트리가 아니라고 가정하면, 선택한 간선들 중에서 최소 스패닝 트리에 포함되지 않는 간선들이 존재할 것이다. 이중 가중치가 가장 작은 간선 하나를 선택해서 $e$라고 하자. $e$는 최소 소패닝 트리에 포함되지 않으므로 $e$가 연결하는 두 정점은 최소 스패닝 트리에서 다른 간선들을 통하여 연결되어 있어야 한다. 그런데 그 경로에 포함되는 간선들 중에는 가중치가 $e$의 가중치 이상인 간선이 하나 이상 존재해야 한다. (그렇지 않다면 $e$가 크루스칼 알고리즘에 의해 선택될 일이 없다.) 그런 간선을 하나 선택한 후 최소 스패닝 트리에서 제거하고 $e$를 최소 스패닝 트리에 추가한 경우, 최소 스패닝 트리에 포함되는 간선들의 가중치 합은 동일하거나 더 작아진다. 두 경우 모두 간선 하나를 바꾼 나중 스패닝 트리가 최소 스패닝 트리가 될 수 있으므로 모순이며, 이는 크루스칼 알고리즘으로 찾은 스패닝 트리가 항상 최소 스패닝 트리 중 하나라는 것을 증명한다.

 

다음으로 구현 방법을 설명할 차례인데, 정점들이 선택된 간선들을 통해서 연결되어 있는지를 빠르게 확인하는 데는 앞에서 설명한 유니온-파인드가 적합하다. 유니온 파인드를 이용하여 정점들을 묶어 주면 최소 스패닝 트리를 구할 수 있다. 구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
struct edge{int u, v, w, select;}w[100005];
int p[100005];
int C(edge a, edge b){return a.w < b.w;}
int _union(int x, int y)
{
    if(x != p[x] || y != p[y])return p[x] = p[y] = _union(p[x], p[y]);
    return p[y] = x;
}
int _find(int x)
{
    if(x != p[x])return p[x] = _find(p[x]);
    return x;
}
int main()
{
    int m, n, x, y, z;
    cin >> n >> m;
    iota(p, p + n + 1, 0);
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        w[i] = {x, y, z, 0};
    }
    sort(w, w + m, C);
    for(int i = 1; i <= m; i++)
    {
        if(_find(w[i].u) != _find(w[i].v))
        {
            _union(w[i].u, w[i].v);
            w[i].select = 1;
        }
    }
}

가중치의 총합을 구하는 등의 추가적인 부분은 필요한 대로 구현하면 된다.

 

[연습문제]

 

BOJ 1197. 최소 스패닝 트리 (Gold IV)

최소 스패닝 트리를 구하면 된다.

 

BOJ 1647. 도시 분할 계획 (Gold IV)

최소 스패닝 트리에서 가중치가 가장 큰 간선을 제외한 나머지 간선들의 가중치 합을 구한다.

 

BOJ 4386. 별자리 만들기 (Gold IV)

각 별을 정점으로 두면 두 정점 사이에 별 사이의 거리가 가중치인 간선이 있는 완전 그래프가 생긴다. 이 그래프의 최소 스패닝 트리를 구한다.

 

BOJ 20335. Generators (Gold I)

중앙 발전소를 $0$번 정점, 각각의 발전소를 $1$부터 $n$번 정점으로 생각하면 $0$번 정점과 $c_i$번 정점을 연결하는 간선의 가중치가 $a_i$, $i$번 정점과 $(i\,\bmod\, n + 1)$번 정점을 연결하는 간선의 가중치가 $b_i$인 그래프를 만들 수 있다. 이 그래프의 최소 스패닝 트리를 구하면 된다.