[Algorithm][Template] 크루스칼 알고리즘

📌 신장트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

크루스칼 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘, Union-FInd를 이용

 

1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

    2-1) 사이클 발생하지 않는 경우 : 최소 신장트리에 포함시킨다.

    2-2) 사이클이 발생하는 경우 : 최소 신장트리에 포함시키지 않는다.

3) 모든 간선에 대하여 2번의 과정을 반복한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

// 노드의 개수(v)와 간선(e)의 개수
// 노드의 개수는 최대 100000개라고 가정
int v, e;
int parent[100001];

// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
     if (parent[x] != x) {
         parent[x] = findParent(parent[x]);
     }
     return parent[x];
 }

// 두 원소가 속한 집합을 합치기
void unionParent(int x, int y) {
    x = findParent(x);
    y = findParent(y);

    if (x < y) {
        parent[y] = x;
    }
    else {
        parent[x] = y;
    }
}

int main(void) {
    vector<tuple<int, int, int> > edge;

    cin >> v >> e;

    // 부모테이블 상에서, 부모를 자기 자신으로 초기화
    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    // union 연산을 각각 수행
    for (int i = 0; i < e; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        edge.push_back(make_tuple(d, a, b));
    }

    // 간선 거리별 오름차순 정렬
    sort(edge.begin(), edge.end()); // greater<int>()

    int sum = 0;
    for (auto t : edge) {
        int a, b, d;
        tie(d, a, b) = t;
        if (findParent(a) != findParent(b)) {
            unionParent(a, b);
            sum += d;
        }
    }
    
    cout << sum << endl;

    return 0 ;
}

🛑 유의사항 : template에서 사용한 tuple은 c++11버전에서만 사용할 수 있다.