[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm), C++

크루스칼 알고리즘

크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 최소 신장 트리를 구하는 방법 중 하나입니다.

 

MST는 간선 가중치의 합이 최소, 사이클이 발생하지 않는다는 특징을 이용하여,

그래프의 전체 간선 중에서 사이클이 발생하지 않으며 가중치가 가장 작은 간선을 선택하며 MST를 완성합니다.

 

1. 그래프의 간선을 가중치 오름차순으로 정렬합니다.
2. 정렬된 순서대로 하나씩 해당 간선이 사이클을 발생하시키는지 확인합니다.
3. 사이클이 발생하지 않는다면 MST 간선 집합에 해당 간선을 추가합니다.
4. 2, 3번의 과정을 간선의 개수가 n-1이 될 때까지 반복합니다.

 

구현 방법

간선을 이루는 두 노드가 이미 같은 집합이라면 해당 간선을 MST 간선 집합에 추가했을 때 사이클이 발생합니다.

 

0-4 간선 선택 예시)

 

{ 0, 1, 2, 3, 4 }가 같은 집합일 때,

0과 4번 노드는 같은 집합이기 때문에 0-4 간선을 MST간선에 추가할 수 없습니다.

 

 

{ 0, 1 } , { 2, 3, 4 } 집합일 때

0과 4가 다른 집합에 속해있기 때문에 0-4 간선을 MST 간선에 추가할 수 있습니다.

 

 

 

간선을 이루는 두 노드가 같은 집합인지 확인하기 위해서는 Union-Find 알고리즘을 활용합니다.

for (Edge e : edges)
{
    int rootTo = Find(e.to);
    int rootFrom = Find(e.from);
    if (rootTo == rootFrom) // 같은 집합인지 확인 
        continue; // 같은 집합이라면 해당 간선 건너뜀

    Union(rootTo, rootFrom); 같은 집합이 아니라면 Union으로 합침
}

 

 

 

 

 

 

예시를 들어 전체적인 과정을 알아보겠습니다.

 

(0-5) 간선

 

(2-3) 간선

 

 

(1-6) 간선

 

(1-2) 간선

 

 

(3-6) 간선

3 과 6은 이미 같은 집합에 속해 있기 때문에 해당 간선을 MST 간선에 추가할 수 없습니다.

 

 

(4-3) 간선

 

(4-6) 간선

4와 6은 이미 같은 집합에 속해있기 때문에 해당 간선을 MST 간선에 추가할 수 없습니다.

 

 

(5-4) 간선

 

간선의 개수가 6(n-1)개가 되었으므로 반복을 종료합니다.

 

위에서 선택되어 MST 에 추가된 간선들이 최소신장트리를 이루게 됩니다.

 

 

 

관련 문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

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

using namespace std;

struct Edge
{
    int from;
    int to;
    int weight;
};

bool operator<(const Edge& a, const Edge& b)
{
    return a.weight < b.weight;
}

int v, e;
vector<Edge> edges;
vector<int> parent;

int Find(int x)
{
    if (parent[x] == x)
        return x;
    else 
        return parent[x] = Find(parent[x]);
        
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);

    if (a == b)
        return;

    parent[a] = b;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> v >> e;
    edges.reserve(e);
    parent.resize(v+1);
    for (int i=0; i<e; ++i)
    {
        int a, b, weight;
        cin >> a >> b >> weight;
        if (a > b)
            swap(a, b);

        edges.push_back({a, b, weight});
    }


    for (int i=1; i<v+1; ++i)
    {
        parent[i] = i;
    }
    
    sort(edges.begin(), edges.end(), less<Edge>());
    
    int edgeCnt = 0;
    int totalCost = 0;

    for (Edge e : edges)
    {
        int ptrTo = Find(e.to);
        int ptrFrom = Find(e.from);
        if (ptrTo == ptrFrom)
            continue;

        Union(ptrTo, ptrFrom);
        ++edgeCnt;
        totalCost += e.weight;

        if (edgeCnt == v)
            break;
    }

    cout << totalCost << endl;
    return 0;
}