[MST] 크루스칼 알고리즘

[MST] 크루스칼 알고리즘

Kruskal Algorithm

최소 스패닝 트리 구하는 알고리즘 중 하나

다른 알고리즘으로는 Prim (프림) 알고리즘이 있다

최소 스패닝 트리는

사이클을 형성하지 않고 가장 적은 가중치로 이루어진 트리이다

크루스칼은 간선을 기준으로 트리를 형성해 나가는 알고리즘이다.

자세한 설명은 [참고] 이 곳이 설명이 자세하고 그림이 있어 이해하기 좋다

크루스칼은 dfs 또는 Union-find을 이용하여 구현할 수 있다

코드를 간단하게 하고 싶어서 Union-find을 이용하여 구현해 보았다.

간선을 오름차순으로 정렬하여야 하는데 입력받을 때 priority_queue에 넣어서 따로 정렬을 해주지 않았다.

만약 C로 구현할 필요가 있다면 구조체를 선언하고, 정렬알고리즘을 따로 구현하기만 하면 된다. vector도 그냥 배열에 추가하는 방식으로 수정

priority_queue는 기본 내림차순 정렬되어 있기 때문에 -1을 곱해주어 거꾸로 정렬되게 하였다.

간선이 작은 순으로 queue에서 꺼내서 간선과 연결된 정점들이 같은 set을 형성하는지 확인한 후에 아니라면 그 둘을 연결시켜 준다.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int n;
priority_queue<pair<int, pair<int, int> > > que;
vector<pair<pair<int, int>, int> > ans;
int parent[1001];
 
void init()
{
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}
 
void input()
{
    int m;
    int one, two, w;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &one, &two, &w);
        que.push(make_pair(w * -1, make_pair(one, two)));
    }
}
 
int find(int node)
{
    if (parent[node] == node)        return node;
    return parent[node] = find(parent[node]);
}
 
void kruskal()
{
    init();
 
    while (!que.empty()) {
        int w = que.top().first * -1;
        int one = que.top().second.first;
        int two = que.top().second.second;
        que.pop();
 
        if (find(one) != find(two)) {
            ans.push_back(make_pair(make_pair(one, two), w));
            parent[find(one)] = find(two);
        }
    }
}
 
void print()
{
    printf("size : %d\n", ans.size());
 
    for (int i = 0; i < ans.size(); i++) {
        printf("%d - %d : %d\n", ans[i].first.first, ans[i].first.second, ans[i].second);
    }
}
 
int main()
{
    input();
 
    kruskal();
 
    print();
 
    return 0;
}