128. Borůvka's Algorithm

보르부카 알고리즘(Borůka's Algorithm) 또는 솔린 알고리즘(Sollin's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 세 번째 알고리즘이며 다음과 같이 작동한다.

    1. 각각의 컴포넌트에 연결된 간선들 중 가중치가 가장 작은 간선을 하나씩 선택한다.

    2. 간선을 차례로 최소 스패닝 트리에 추가하는데, 간선이 연결하는 두 정점이 이미 같은 컴포넌트에 존재한다면 추가하지 않는다.

    3. 컴포넌트가 하나로 줄어들 때까지 1번과 2번 과정을 반복한다.

 

이번에도 설명이 짧게 끝났다. 다시 예시를 가지고 살펴보자.

처음에는 정점들이 모두 다른 컴포넌트에 존재하므로, 각 정점과 연결된 간선들 중 가중치가 가장 작은 것 하나를 모두 고른다.

$\text{A}: \text{D}(2)\\ \text{B}: \text{A}(8)\\ \text{C}: \text{E}(5)\\ \text{D}: \text{A}(2)\\ \text{E}: \text{D}(4)\\ \text{F}: \text{H}(2)\\ \text{G}: \text{I}(5)\\ \text{H}: \text{F}(2)\\ \text{I}: \text{H}(4)\\$

연결하는 정점들의 컴포넌트가 서로 다른 간선들을 차례로 추가하면 컴포넌트의 개수는 $2$개로 줄어든다.

다시 간선을 선택한다. 각 컴포넌트별로 다른 컴포넌트와 연결된 간선들 중 가중치가 가장 작은 것 하나를 선택하면 다음과 같다.

$\text{D}: \text{F}(2)\\ \text{F}: \text{D}(2)$

이 간선을 최소 스패닝 트리에 추가한다.

컴포넌트가 $1$개가 되었으므로 알고리즘을 종료한다.

---

알고리즘의 시간 복잡도를 계산하면, 간선들을 스패닝 트리에 추가하는 과정을 한 번 진행할 때 컴포넌트의 개수가 절반 이하로 줄어들기 때문에 그래프의 정점 수가 $n$일 때 이 과정은 최대 $\lg n$번 반복되고, 각 과정에서 $m$개의 간선을 확인하며 간선이 연결하는 집합을 확인하는 것은 유니온-파인드를 사용하면 상수 시간에 할 수 있으므로 전체 시간복잡도는 $O(m \lg n)$이다.

 

구현은 다음과 같다. 무한대를 나타내는 값으로 $2^{30}$이 사용되었는데, 만약 가중치가 이 값을 넘어갈 수 있다면 무한대를 나타내는 값도 바꿔 주어야 한다. [샘플 코드]

#import<bits/stdc++.h>
using namespace std;
int p[100005], tv[100005], tx[100005], ty[100005];
vector<pair<int, int>>e[100005], mst[100005];
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 c, 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;
        e[x].push_back({y, z});
        e[y].push_back({x, z});
    }
    for(c = n; c > 1;)
    {
        fill(tv, tv + n + 1, 1 << 30);
        for(int i = 1; i <= n; i++)
        {
            for(auto &pp: e[i])
            {
                int g1 = _find(i), g2 = _find(pp.first);
                if(g1 != g2)
                {
                    if(pp.second < tv[g1])
                    {
                        tx[g1] = i;
                        ty[g1] = pp.first;
                        tv[g1] = pp.second;
                    }
                    if(pp.second < tv[g2])
                    {
                        tx[g2] = i;
                        ty[g2] = pp.first;
                        tv[g2] = pp.second;
                    }
                }
            }
        }
        for(int i = 1; i <= n; i++)
        {
            if(tv[i] < 1 << 30 && _find(tx[i]) != _find(ty[i]))
            {
                mst[tx[i]].push_back({ty[i], tv[i]});
                mst[ty[i]].push_back({tx[i], tv[i]});
                _union(tx[i], ty[i]);
                c--;
            }
        }
    }
}