Kruskal’s Alogorithm

kruskal 알고리즘은 greedy approach를 이용한 알고리즘이다.
그래프가 주어지고, 노드와 노드 사이에 가중치가 있을 때, 가장 최소의 혹은 가장 최대의 비용을 가지게 되는 트리를 구하는 알고리즘이다.

kruskal의 가장 핵심은 union과 find 함수에 있다고 봐도 과언이 아니다.
union과 find를 이용한 자료 구조를 disjoint set forest라고 부르기도 한다.
특히나, 여기에서는 weighted_union, collapsing rule을 적용한 find 함수로 구현되었다.
코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_FILENAME_LENGTH 50
void initialize(int *parent, int n);
int find(int *parent, int i);
void union_set(int *parent, int i, int j);
int main() {
    FILE *fp_input;
    char file_name[MAX_FILENAME_LENGTH];
    int num_of_vertex, num_of_edge;
    int *parent;
    int i, p, q, weight, counter;
    int parent_node1, parent_node2;
    printf("input file name?\n=> ");
    scanf("%s", file_name);
    fp_input = fopen(file_name, "r");
    if (fp_input == NULL) {
        fprintf(stderr, "FILE <%s> open error.\n", file_name);
        return -1;
    }
    fscanf(fp_input, "%d %d", &num_of_vertex, &num_of_edge);
    parent = (int *) malloc(sizeof(int) * (num_of_vertex + 1));
    if (parent == NULL) {
        fprintf(stderr, "memory allocation error : int *parent\n");
        return -1;
    }
    initialize(parent, num_of_vertex);
    counter = 0;
    for (i = 0; i < num_of_edge; i++) {
        if (counter == num_of_vertex - 1) {
            break;
        }
        fscanf(fp_input, "%d %d %d", &p, &q, &weight);
        parent_node1 = find(parent, p);
        parent_node2 = find(parent, q);
        if (parent_node1 != parent_node2) {
            union_set(parent, parent_node1, parent_node2);
            printf("( %d %d %d )\n", p, q, weight);
            counter++;
        }
    }
    fclose(fp_input);
    free(parent);
    return 0;
}
void initialize(int *parent, int n) {
    int i;
    for (i = 0; i < n; i++) {
        parent[i] = -1;
    }
}
int find(int *parent, int i) {
    int r, s;
    for (r = i; parent[r] >= 0; r = parent[r]) { 
        ;
    }
    while (i != r) {
        s = parent[i];
        parent[i] = r;
        i = s;
    }
    return r;
}
void union_set(int *parent, int i, int j) {
    int temp = parent[i] + parent[j];
    if (parent[i] > parent[j]) {
        parent[i] = j;
        parent[j] = temp;
    } else {
        parent[j] = i;
        parent[i] = temp;
    }
}
  • main함수

    코드에서는 인풋을 file을 통해서 받고, 아웃풋은 표준 출력으로 한다.
    버텍스와 엣지의 수를 입력 받는다.
    int *parent는 union-find 함수의 쉬운 구현을 위해 1차원 동적 배열로 선언한다.
    로직으로는, 파일로부터 그래프의 정보를 먼저 받아온 뒤에, parent 배열의 사이즈를 동적할당 하는 로직이다.
    parent 배열을 초기화 해 주고, kruskal 알고리즘을 시작한다.

kruskal 알고리즘의 속도 개선을 위해서, counter를 사용한다.
kruskal 알고리즘의 결과는 항상 노드의 수 -1 개 만큼의 간선을 연결하면 되기 때문에, 이미 노드의 수 – 1개 만큼의
간선을 연결한 경우 더이상 union-find를 실행할 필요가 없다.
따라서 kruskal 알고리즘을 구현하는 for문의 가장 처음에 if 문으로 종료조건을 붙인다.

종료조건 이후에는, 파일로부터 간선의 정보를 읽어온다.
정보는 순서대로, 출발 노드, 도착 노드, 가중치이다.
그리고 각각의 노드들에 대해 root 노드를 탐색한다.
탐색은 find 함수를 통해서 하고, return 값으로 root 노드의 번호를 받는다.

그리고 난 뒤 출발 노드와 도착 노드의 root 노드가 각각 같지 않은 경우에는,
이 두 노드를 union해 주고, 표준 출력으로 출발 노드, 도착 노드, 가중치를 출력해준다.
만약, 출발 노드와 도착 노드의 root 노드가 모두 같을 경우에는 결국 연결 시 cycle을 형성하게 된다는 의미이므로, union하지 않고 그냥 지나간다.

  • initialize 함수

    parent 배열의 초기값을 모두 -1로 해 준다.
    코드의 예시에서는 for문을 돌면서 처음부터 끝까지 각각 -1로 설정하지만, 다음과 같은 코드로 대체할 수도 있다.

    #include <memory.h>
    
    memset(parent, -1, sizeof(int) * (n + 1) );

     

  • find 함수

    find 함수의 처음 for문 헤더가 중요하다.
    for문을 돌면서, 해당 노드가(파라미터로 받은 i 노드) 음수가 아니라면(root가 아니라면) r 에다가 그 값을 기록하는 for문이다.
    처음에 parent 배열을 모두 -1로 설정했기 때문에, 모든 노드들은 간선이 연결되지 않은 상태, 즉 -1을 가진 상태가 된다.
    (parent의 초기값이 -1 이라는 것은 모든 노드가 root라는 의미이다.)
    그런데, find-union을 통해서 연결이 된 경우에는 root노드를 제외하고는, 양의 값, 즉 연결된 상대 노드의 번호(child)를 가지게 된다.
    for문을 돌면서 그 노드의 root노드(음수로 기록된)를 찾는 기능을 한다.
    사실상 여기까지가 단순한 find 함수를 구현하고자 한다면 끝이 될 수도 있다.
    하지만 이렇게 될 경우에, 연속적인 인풋이 있을 경우 트리의 입장에서 봤을 때, 트리가 한쪽으로 치우치게 되는 worst case를 만들 가능성이 있다.
    이를 변질 트리(degenerate tree)라고 한다.
    트리의 키가 늘어나는 것은 결코 시간 복잡도 측면에서 좋은 코드라고 하기 어렵기 때문에 이 부분의 해결을 위해 while문이 추가되었다.
    이 것을 collapsing rule이라고도 한다.
    find를 하면서, root가 아닌 노드, 즉 음수값이 아닌 노드들을 root의 child 노드로 변경해주는 작업을 while문에서 하고 있다.

  • union_set 함수

    마지막으로 union_set 함수에서는 파라미터로 연결할 두 노드를 받습니다.
    그리고 temp 변수를 통해, 해당 노드의 자식 노드, 즉 연결된 노드의 숫자를 음수로 기록하는 방법입니다.
    union은 root와 root만을 연결하기 때문에 이와 같은 방법이 가능해지게 됩니다.
    그리고 가중치를 부여하여 if문의 parent[i] > parent[j] 가 참이 된다는 뜻은, i 노드의 자식이 j 노드의 자식 수보다 적다는 것을 의미합니다.
    다시 말해, i 노드가 자식을 j 노드보다 적게 가지고 있다는 뜻입니다.
    이런 경우에는 i 노드를 j에 붙여주고, 반대라면 j 노드를 i에 붙여줍니다.
    이렇게 union 하는 것을 weighted_union 이라고 합니다.

  • 예시로 작성된 코드의 file input 양식은 다음과 같다.
    첫 줄에 노드의 수와 간선의 수를 띄어쓰기를 구분하여 입력한다.
    그 다음 줄부터 출발 노드, 도착 노드, 가중치 순으로 띄어쓰기를 구분하여 정수로 입력한다.
    예를 들면 다음과 같다.

    4 5
    1 2 1
    2 3 2
    3 4 3
    4 1 4
    4 2 5
  • 코드에서는 input data가 모두 가중치를 기준으로 오름차순 정렬되어 있다는 가정하에 작성되었다.
    만약, input이 random하게 작성되어야 하는 프로그램의 경우, kruskal 알고리즘을 시작하기 전에 먼저 sorting 해 주는 코드가 추가되어야 한다.

댓글 남기기