[자료구조] MST를 구할 때 사용하는 크루스칼 알고리즘(Kruskal)

설명에 앞서, Union - Find 연산에 대해서 학습을 해야하는데, 이 부분은 제가 봤던 유튜브로 대체하겠습니다.

https://www.youtube.com/watch?v=eTaWFhPXPz4

이것과 Optimized Union/FInd를 보시고

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

1717번: 집합의 표현

이 문제를 풀어서 제대로 이해했나 확인해보시면 됩니다.

​

Kruskal 알고리즘을 왜 쓰는가?

- MST를 구할때 사용하는 알고리즘 입니다.

Union-Find를 안다는 가정하에 구현이 Prim에 비해서 조금 더 쉽습니다.

 

- 언제 사용하는가?

무방향(undirected) 그래프에서만 사용이 가능합니다. 또한 가중치가 음수,양수가 상관이 없이 구할 수 있습니다.

위 2가지 성질이 굉장히 중요하다고 생각합니다.

​

- 왜 무방향에서만 사용이 가능할까요?

-> union 연산이 cycle을 확인하는 작업인데, 방향이 있는 그래프여도 무방향처럼 인식을해서 사이클이 있다고 판단을 해버립니다.

이건 사이클이 없지만, 무방향으로 생각해보면 사이클이 있는것처럼 나옵니다.

​

- 왜 양수 음수 가중치가 상관이 없을까요?

특정 지점에서 모든 지점까지의 최단거리를 구하는 알고리즘인 다익스트라는 가중치를 갱신하는 과정에서

if( V[cur] > V[prev] + weight) 음수때문에 이상하게 변경될 수 있습니다.

하지만 MST는 말그대로 스패닝 트리중에 최소를 구하면 되므로, 음수 간선이면 그 자체로 최소가 됩니다.

​

시각적으로 설명해드리고 싶지만, 시간이 없어서...

​

크루스칼 알고리즘 순서

​

1. 모든 가중치를 순서대로 받아서 오름차순으로 정렬을 한다.

2. 가장 작은 가중치를 골라서, 그 edge를 구성하는 Vertex를 연결했을때 cycle이 있는지 체크한다.

3. cycle이 없으면 가중치를 확정하고, cycle이 있으면 continue 한다.

4. 이 과정을 모든 정점이 다 방문될때까지 반복한다.

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

1197번: 최소 스패닝 트리

이 문제로 여러분이 푼것이 맞는지 확인할 수 있습니다.

​

1. 모든 가중치를 받아서 오름차순으로 정렬한다.

-> 이 방법은 c++의 tuple을 이용해도 되고, struct로 해도 됩니다. 저는 두가지 방법으로 모두 해봤습니다.

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef struct _Node{
    int u;
    int v;
    int w;
}Node;

Node Edge[100005];
int ds[10005];
int height[10005];
int find(int a)
{
    if(!ds[a]) return a;
    return ds[a] = find(ds[a]);
}

void merge(int f, int s)
{
    if(f != s)
    {
        if(height[f] == height[s]){
            ds[s] = f;
            height[f]++;
        }else if(height[f] > height[s]){
            ds[s] = f;
        }else{
            ds[f] = s;
        }
    }
}
bool comp(Node& e1, Node& e2)
{
    return e1.w < e2.w;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 가중치가 낮은 기준으로 정렬
    // 다익스트라는 pq <weight, vertex>로 넣었음
    // 여기서는 a,b,c라는 정보가 필요함.
    
    int V,E;
    int u,v,w;
    int f,s;
    int sum = 0;
    int cnt = 0;
    cin >> V >> E;
    for(int i = 0; i < E; i++)
    {
        cin >> Edge[i].u >> Edge[i].v >> Edge[i].w;    
    }

    sort(Edge, Edge+E, comp);
    // 가중치가 최소인걸로 정렬 완료
    
    for(int i = 0; i < E; i++)
    {
        u = Edge[i].u;
        v = Edge[i].v;
        w = Edge[i].w;
        // u,v가 연결되어있나?
        f = find(u);
        s = find(v);
        if(f != s) // 연결 X
        {
            merge(f,s);
            sum += w;
            cnt++;
        }else continue;// 사이클이면 ㅌㅌ
        // 연결안되어있으면 합쳐
        if(cnt == V-1) break;

    }
    cout << sum;
    
    return 0;
}

보시면 뭐 엄청 대단한 자료구조를 쓴게 없습니다.

하지만 Prim알고리즘은 힙자료구조인 priority_queue를 사용해야합니다.

따라서 C로 맨바닥에 짰을때, 그나마 할 수 있는게 kruskal 입니다.

​

​

시간복잡도는 어떻게 될까요?

sort -> O(ElogE)

for문 -> O(E)

O(E)에 대해서 의문이 있었는데, union-find가 logV이라는데 뭔소릴 하는거냐? 할 수 있습니다.

경로 압축과, rank를 이용해서 트리를 밸런스있게 만들어주면 결국 O(1)수준입니다.

​

This makes disjoint-set operations practically amortized constant time. The combination of path compression, splitting, or halving, with union by size or by rank (위키피디아)

​

저기서 경로압축만 하더라도 문제가 풀리는데 왜 height비교는 하는거지? 생각이 들었습니다.

실제로 skewed 한 형태일때 1->2->3->4 1번을 선택하면 absoulute parent를 참조하는데 O(V)이 들게 됩니다. 저렇게 rank를 이용해서 트리를 미리미리 짧게 구성해주어야 엄청나게 빠른시간안에 할 수 있게 됩니다. 직접 종이에 몇개 그려보면 알 수 있습니다.

​

​

따라서 최종적으로 O(ElogE)가 나오게 됩니다.

나중에 Prim와 Kruskal의 차이에 대해서 생각해보게 되는데, 여기를 보면 E에 굉장히 영향을 많이 받는걸 볼 수 있습니다. 따라서 Edge의 개수가 적을수록 Kruskal의 효율이 좋고, 많으면 많을수록 Prim이 좋다는걸 알게 될 것입니다.

​

감사합니다