Kruskal 알고리즘

Goal

• Kruskal 알고리즘에 대한 이해
• Kruskal 알고리즘을 구현할 수 있다.
• Kruskal 알고리즘이 사용되는 예시를 들 수 있다.

사전 필요 지식

• 최소 신장 트리
• Union-Find

---

크루스칼 알고리즘(Kruskal's algorithm)

탐욕적인 방법(Greedy Method)을 이용하여 모든 정점을 최소 비용을 갖는 간선으로 연결하는 알고리즘
*탐욕적인 방법 : 결정을 할 때마다 "그 순간에 최적"이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것

순간의 최적이라고 생각했던 것들을 모아 최종적인 결과를 도출해 낼 때, 그것이 "궁극적으로 최적"이라는 보장은 없다.
하지만!! 다행히 Kruskal 알고리즘은 궁극적으로도 최적의 해를 구하는 것으로 증명 되었다.

 

Kruskal 알고리즘은 최소 신장 트리(MST, Minimum Spanning Tree)를 구할 때 사용되는데,

최소 신장 트리(MST)를 구하려면 다음과 같은 조건을 반드시 만족 해야한다.

 

최소 신장 트리의 조건

1. 반드시 (n-1)개의 간선만 사용해야 한다.
2. 사이클을 포함해서는 안된다.
3. 간선 가중치 합이 최소이어야 한다.

Kruskal 알고리즘 동작 방식

Kruskal 알고리즘은 각 단계에서 사이클을 이루지 않는 최소 비용의 간선을 선택한다.

 

Kruskal 알고리즘 동작 순서

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 작은 간선 e를 뽑는다
3. e를 트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.
4. 사이클이 생기지 않으면 트리에 삽입한다.
5. 트리의 간선 n-1개가 될 때까지 2번 과정을 반복한다. (간선이 n-1개가 되면 최소 신장 트리가 된다)

위 과정에서 Cycle확인을 위해서 Union-Find연산을 사용한다.

 

다음 그림은 Kruskal알고리즘을 사용해서 MST를 구하는 과정을 나타낸다.

 

 

 

중요 포인트

1. 각 단계에서 최소 비용 간선을 선택한다.
2. Cycle 확인 (Union-Find 연산을 통해 확인한다)

Kruskal 알고리즘의 시간 복잡도

Kruskal 알고리즘 의사 코드

• 초기화(make-set)에 필요한 계산량은 O(V)
• 간선 정렬 시간 복잡도 : O(ElogE)
• 모든 간선 E에 대해서 find, union 연산 수행 : O(ElogE) 
  • * find, union 연산의 시간 복잡도 : O(logE)

=> 최종 시간 복잡도 : O(ElogE)

 

Kruskal 알고리즘의 구현

(BOJ 1197 문제)

#include<cstdio>
#include<algorithm>

#define MAX 100001

using namespace std;

struct edge
{
    int from, to, weight;

    bool operator<(const edge& e2)
    {
        return weight < e2.weight;
    }
};

int N, M;
int parent[MAX];
edge E[100001];

int find(int x) // find parent
{
    if (x == parent[x])
        return x;
    else
    	// return find(parent[x]); // 경로 압축 안하는 경우
        return parent[x] = find(parent[x]); // 경로 압축 하는 경우
}

void unite(int x, int y)
{
    x = parent[x];
    y = parent[y];
    parent[x] = y;
}

int main(void)
{
    scanf("%d %d", &N, &M);
    
    //make-set
    for(int i = 1; i <= N; i++)
        parent[i] = i;

    // edge init
    int u, v, w; // from vertex, to vertex, weight
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &u, &v, &w);
        E[i] = { u, v, w };
    }

    // sort by cost
    sort(E, E + M);

    int i = 0;
    int cnt = 0;
    int sum = 0;

    while (cnt < N-1)
    {
        u = E[i].from;
        v = E[i].to;
        if (find(u) != find(v))
        {
            unite(u, v);
            cnt++;
            sum += E[i].weight;
        }
        i++;
    }
    printf("%d", sum);

    return 0;
}

 

Kruskal 알고리즘 정리

• 최소 신장 트리(MST)를 구할 때 사용하는 알고리즘이다.
• 간선을 기준으로 트리를 확장해 나간다.
• 시간 복잡도 O($E\log_2{E}$)
• 희소 그래프(Sparse Graph)에 적합한 알고리즘

---

References

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

https://ratsgo.github.io/data%20structure&algorithm/2017/11/28/MST/

https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

C++로 쉽게 풀어쓴 자료구조