MST: Kruskal 알고리즘

크루스칼 알고리즘은 여러 개의 트리를 하나의 트리로 키워나가는 알고리즘이다.

 

간선의 길이가 짧은 엣지 순으로, 두 정점 {u,v}가 서로 다른 집합에 있으면 연결한다.

슈도 코드는 다음과 같다.

MST = ∅
모든 v ∈ G.Vertex에 대해:
    v가 속한 집합을 자기 자신(v)로 초기화

(u, v) ∈ G.Edge 의 가중치가 증가하는 순서대로 정렬;

정렬된 (u, v) ∈ G.Edge 에 대해 n-1개의 Edge가 추가될 때 까지:
    if FIND-SET(u) ≠ FIND-SET(v):  // 정점 u, v가 속한 집합이 다르면 (서로 연결이 안됐으면)
        MST = MST ∪ {(u, v)}  // MST에 엣지 추가
        UNION(FIND-SET(u), FIND-SET(v))  //u, v 같은 집합에 추가 (서로 연결)

return MST

 

 

 

* 빨간 간선은 현재 선택된 간선, 파란 간선은 아직 선택되지 않은 간선, 검은 간선은 트리에 추가된 간선을 뜻한다.

 

1 -> 2

3 -> 4 순으로 진행

 

총 n-1개(6개)의 엣지를 추가하면 MST가 완성된다.

 

완성된 MST

 

집합 표현을 위해 Disjoint-Set을 이용한 코드는 다음과 같다.

#include <cstdio>
#include <algorithm>
#include <vector>

struct Edge {int u,v,w;
    Edge()=default;
    Edge(int u,int v,int w):u(u),v(v),w(w){};
    bool operator<(const Edge& a) const
    { return this->w < a.w; }
};
int N,K;
using namespace std;

int get_parent(int parent[],int x) { // x가 속한 집합을(root를) 찾음
    while(parent[x] != 0) {
        if(parent[x] == x) break;
        x = parent[x];
    }
    return x;
}

void make_union(int parent[],int u, int v) { // 두 정점을 같은 집합에 추가(edge 추가)
    int p_u, p_v;
    p_u = get_parent(parent,u);
    p_v = get_parent(parent,v);
    parent[p_v] = p_u;
}

bool find_set(int parent[],int u, int v) { // u, v가 속한 집합이 서로 다르면 추가 가능(true) 같으면 (false)
    int p_u, p_v;
    p_u = get_parent(parent,u);
    p_v = get_parent(parent,v);
    if(p_u != p_v)
        return true;
    else
        return false;
}

int main() {
    scanf("%d%d",&N,&K);
    int parent[N+1]; // 정점은 1번부터 시작
    vector<Edge> G;

    for(int i=0;i<K;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G.push_back({u,v,w});
    }
    sort(G.begin(),G.end()); // 오름차순으로 정렬
    int sum = 0;
    for(int i=0;i<=N;i++){
        parent[i] = i; // 집합 초기화
    }
    for(int i=0;i<G.size();i++){
        // Edge의 개수가 n-1개면 MST 완성
        if(find_set(parent,G[i].u,G[i].v)) { // 서로 다른 집합이면
            make_union(parent,G[i].u,G[i].v); // 두 집합 합치기(edge 생성)
            sum += G[i].w;
        }
    }
    printf("%d",sum);
}