Kruskal's MST algorithm

Kruskal's MST algorithm은 Minimum Spanning Tree를 구하는 알고리즘 중 하나이다.

 

Minimum Spanning Tree는 우리말로 번역하면 최소 신장 트리라고 하는데, 여기서 신장(伸張)은 펼 신, 길 장, 이는 뻗어 나간다는 의미가 있다. 고로 모든 노드를 거치는 나무, 뻗어 나가는 나무, 생성 나무라고도 한다.

 

Kruskal's MST algorithm은 탐욕적인 방법(Greedy method)을 이용하고, 순간마다 제일 나은 선택을 한다. 그러나 제일 나은 선택이라고 생각했던 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 전체적인 관점에서 최적이라는 보장은 없다. 따라서 이 알고리즘은 항상 최적의 해답을 주는지를 반드시 점검해야 하는데, 다행히 Kruskal’s MST algorithm은 최적의 해답을 주는 것으로 증명되어 있다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50 // 정점의 최대 숫자

int parent[MAX_VERTICES]; // 정점의 root

// parent 배열을 -1로 초기화
void set_init(int n){ 
    for(int i = 0; i < n; i++){
        parent[i] = -1;
    }
}

// 정점의 root를 찾기
int set_find(int curr){       
    if(parent[curr] == -1){
        return curr;
    }
    while(parent[curr] != -1){
        curr = parent[curr];
    }
    return curr;
}

// 정점들을 묶기
void set_union(int a, int b){
    int root1 = set_find(a);
    int root2 = set_find(b);
    if(root1 != root2){
        parent[root1] = root2;
    }
}

// 간선의 구조체
struct Edge{
    int start, end, weight;
};

// 그래프의 구조체
typedef struct GraphType{
    int v, n; // v: 노드의 수 n: 간선의 수
    struct Edge edges[2 * MAX_VERTICES];
} GraphType;

// 그래프의 초기화
void graph_init(GraphType *g){
    g->n = g->v = 0;
    for(int i = 0; i < 2 * MAX_VERTICES; i++){
        g->edges[i].start = 0;
        g->edges[i].end = 0;
        g->edges[i].weight = 999999;
    }
}

// 그래프에서 정점의 숫자를 설정
void set_node(GraphType *g, int n){
    g->v = n;
}

// 그래프에 간선을 삽입
void insert_edge(GraphType *g, int start, int end, int weight){
    if(g->v > 0){
        g->edges[g->n].start = start;
        g->edges[g->n].end = end;
        g->edges[g->n].weight = weight;
        g->n++;
    } else {
        printf("number of vertex is 0\n");
    }
}

// 간선의 비용을 비교하는 함수
int compare(const void *a, const void *b){
    struct Edge *x = (struct Edge *)a;
    struct Edge *y = (struct Edge *)b;
    return (x->weight - y->weight);

}

// kruskal 알고리즘
void kruskal(GraphType *g){
    int edge_selected = 0;
    int uset, vset;
    struct Edge e;

    set_init(g->v);
    qsort(g->edges, g->n, sizeof(struct Edge), compare);
    printf("크루스칼 최소 신장 트리 알고리즘\n");
    int i = 0;
    while(edge_selected < (g->v - 1)){
        e = g->edges[i];
        uset = set_find(e.start);
        vset = set_find(e.end);
        if(uset != vset){
            printf("간선 (%d, %d) %d 선택\n", e.start, e.end, e.weight);
            edge_selected++;
            set_union(uset, vset);
        }
        i++;
    }
}

int main(void){
    GraphType *g;
    g = (GraphType *)malloc(sizeof(GraphType));
    graph_init(g); 
    set_node(g, 7);

    insert_edge(g, 0, 1, 29);
    insert_edge(g, 1, 2, 16);
    insert_edge(g, 2, 3, 12);
    insert_edge(g, 3, 4, 22);
    insert_edge(g, 4, 5, 27);
    insert_edge(g, 5, 0, 10);
    insert_edge(g, 6, 1, 15);
    insert_edge(g, 6, 3, 18);
    insert_edge(g, 6, 4, 25);

    kruskal(g);
    free(g);
    return 0;
}
'''

 

1. 먼저 간선들을 가중치의 오름차순으로 정렬한 후, 가장 가중치가 낮은 간선을 선택

2. 가중치가 낮은 간선을 선택하고 그 양쪽 노드의 root 부분이 같으면 cycle을 이루기 때문에 포함하지 않는다.

3. (1), (2)를 반복하면서 선택한 간선의 개수가 노드의 개수보다 1개 적어지면 종료