MST 최소 신장 트리 Sollin, Boruvka (솔린, 보르부카) 알고리즘 구현

이 게시글에서는 솔린, 해외에서는 보르부카라는 이름으로 더 알려져 있는 MST 생성 알고리즘을 구현해보겠다.

솔린 알고리즘의 간단한 설명

주어진 그래프에서 각 노드들을 트리라 생각한다. 그러면 그래프는 포레스트가 된다.

 

각 트리에서 다른 트리로 연결된 최소 비용 엣지를 택하여 그 엣지로 연결된 두 트리를 union하는 것을 포레스트가 하나의 트리가 될 때까지 반복하면 MST가 완성된다.

 

단계마다 모든 엣지들을 탐색하면서 포레스트에 들어있는 트리의 개수가 절반씩 줄어들다가(한 트리는 다른 트리와 무조건 짝지어지게 됨을 생각하면 이해할 수 있다.) 1개, 즉 MST가 되면 종료하므로 시간 복잡도는 $O(ElogV)$이다.

구현 - 백준 1197번 풀기

union하는 것에서 눈치챌 수 있듯이 솔린 알고리즘도 크루스칼처럼 유니온 파인드를 이용해 구현한다.

 

C++

#include <bits/stdc++.h>
 
using namespace std;
 
int least[10001];
 
struct union_find
{
    vector<int> parent, rank;
 
    union_find(int n): parent(n), rank(n, 1) 
    {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
 
    int find(int v)
    {
        if (parent[v] == v)
            return v;
        
        return parent[v] = find(parent[v]);
    }
 
    void vnion(int u, int v)
    {
        u = find(u), v = find(v);
        
        if (u == v)
            return;
        
        if (rank[u] > rank[v])
            swap(u, v);
        
        parent[u] = v;
 
        if (rank[u] == rank[v])
            ++rank[v];
    }
};
 
int sollin(vector<vector<int>> &edges, int node);
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int v, e;
    cin >> v >> e;
    
    vector<vector<int>> edges;
 
    for (int i = 0; i < e; ++i)
    {
        int s, d, w;
        cin >> s >> d >> w;
 
        edges.push_back({s, d, w});
    }
 
    cout << sollin(edges, v);
}
 
int sollin(vector<vector<int>> &edges, int node)
{
    int ret = 0;
    union_find st(node + 1);
 
    int trees = node;
 
    while (trees > 1) // MST가 되기 전까지 다음 과정을 반복함
    {
        // 최소 가중치 엣지를 저장하는 배열을 초기화
        memset(least, -1, sizeof least);
 
        for (int i = 0; i < edges.size(); ++i)
        {
            int a = st.find(edges[i][0]), b = st.find(edges[i][1]);
                
            // 두 노드가 하나의 트리에 속할 때는 무시한다.
            if (a == b)
                continue;
 
            // 각 노드에 연결된 엣지 중 최소 가중치를 가진 엣지를 저장한다. 
            if (least[a] == -1 || edges[least[a]][2] > edges[i][2])
                least[a] = i;
            
            if (least[b] == -1 || edges[least[b]][2] > edges[i][2])
                least[b] = i;
        }
 
        for (int j = 0; j < node; ++j)
        {
            // 연산할 필요가 없는 엣지는 무시
            if (least[j] == -1)
                continue;
            
            int x = st.find(edges[least[j]][0]), y = st.find(edges[least[j]][1]);
 
            // 이 엣지로 연결된 두 노드가 이미 한 트리에 속하면 무시
            if (x == y)
                continue;
 
            // 그렇지 않으면 MST 간선임으로 ret에 가중치를 더해주고 두 노드를 union
            ret += edges[least[j]][2];
            st.vnion(x, y);
            --trees; // 두 트리가 병합되었으므로 포레스트에 포함된 트리 개수를 하나 줄여준다.
        }
    }
 
    return ret;
}
 

 

 

 

C

#include <stdio.h>
#include <string.h>
 
int least[10001];
int edge[100000][3];
 
typedef struct union_find
{
    int parent[10001], rank[10001];
} union_find;
 
void init(union_find *st)
{
    for (int i = 0; i <= 10000; ++i)
        st->parent[i] = i, st->rank[i] = 1;
}
 
int find(union_find *st, int u)
{
    if (u == st->parent[u])
        return u;
    
    return st->parent[u] = find(st, st->parent[u]);
}
 
void merge(union_find *st, int u, int v)
{
    u = find(st, u), v = find(st, v);
 
    if (u == v)
        return;
    
    if (st->rank[u] > st->rank[v])
    {
        int tmp = u;
        u = v;
        v = tmp;
    }
 
    st->parent[u] = v;
 
    if (st->rank[u] == st->rank[v])
        ++st->rank[v];
}
 
int main()
{
    int v, e;
    scanf("%d %d", &v, &e);
 
    union_find st;
    init(&st);
 
    for (int i = 0; i < e; ++i)
    {
        int s, d, w;
        scanf("%d %d %d", &s, &d, &w);
        edge[i][0] = s, edge[i][1] = d, edge[i][2] = w;
    }
 
    int trees = v;
    int res = 0;
 
    while (trees > 1)
    {
        memset(least, -1, sizeof least);
 
        for (int i = 0; i < e; ++i)
        {
            int x = edge[i][0], y = edge[i][1];
 
            x = find(&st, x), y = find(&st, y);
 
            if (x == y)
                continue;
            
            if (least[x] == -1 || edge[least[x]][2] > edge[i][2])
                least[x] = i;
            if (least[y] == -1 || edge[least[y]][2] > edge[i][2])
                least[y] = i;
        }
 
        for (int j = 0; j < v; ++j)
        {
            if (least[j] == -1)
                continue;
            
            int x = find(&st, edge[least[j]][0]), y = find(&st, edge[least[j]][1]);
 
            if (x == y)
                continue;
            
            res += edge[least[j]][2];
            --trees;
            merge(&st, x, y);
        }
    }
 
    printf("%d", res);
    return 0;
}