[그래프]Kruskal

Kruskal

어떤 그래프로부터 최소 신장 트리(Minimum Spanning Tree)를 도출해낼 때 사용하는 알고리즘

1. 모든 간선을 원소로 갖는 집합 S를 만든다.
2. S가 비어있지 않는 동안
   1. 가작 작은 가중치를 가진 간선 원소를 S에서 가져온다.
   2. 그 간선이 어떤 두 개의 서로 다른 tree를 연결한다면 두 tree를 연결하여 하나의 tree를 만든다.
   3. 그렇지 않다면 해당 간선을 버린다.

위의 프로세스는 Greedy Method 방식으로 진행이 된다.

Greedy Method

• 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
• 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.
• Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.

시간복잡도

O(ElogV)

예시 코드

두 트리를 연결하는 과정에서 union-find 알고리즘을 사용하면 쉽게 구현할 수 있다.

#define MAX_SIZE 100000

typedef struct Edge{
    int from, to, cost;
}Edge;

bool cmp(const Edges &e1, const Edge &e2){
    return e1.cost < e2.cost;
}

//index 0 is not used
int Set[MAX_SIZE + 1]; //소속한 집합의 루트값
vector<Edge> edges;

int find(int n){
    if(Set[n] = n)   return n;
    return Set[n] = find(Set[n]);   //path compression
}

void union(int a, int b){
    int A(find(a));
    int b(find(b));
    if(A != B){
        Set[A] = B;
    }
}

int kruskal(int v, int e){
    int mstCost = 0;
    int selectCnt = 0;
    
    for(int i = 1; i <= MAX_SIZE; i++)    Set[i] = i;
    
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i = 0; i < e; i++){
        if(find(edges[i].from) != find(edges[i].to)){
            mstCost += edges[i].cost;
            selectCnt++;
            union(edges[i].from, edges[i].to);
        }
    }
    
    if(selectCnt == v - 1)    return mstCost;
    else return -1;
}