Prim’s Algorithm

Greedy Approach의 대표적인 알고리즘으로 앞서 소개한 Kruskal 알고리즘과 Prim 알고리즘을 들 수 있다.
Kruskal과 Prim 모두 MST(Minimum Spanning Tree, 최소신장트리) 이다.

Prim 알고리즘의 구현을 위해서 이 전 게시물인 Heap Sort와 Linked List의 코드를 일부 차용하였다.
최소 힙과 인접 리스트를 Prim의 자료구조로 사용하기 위함이다.
(힙과 리스트에 대한 부분은 각각 이전 게시물을 참조.)

Prim 알고리즘의 기본 로직은 다음과 같다.

  1. 인풋 그래프를 각각의 노드에 대한 인접 리스트로 만든다.
    예를 들어, 다음 그림은 아래와 같이 표현된다.

    1번 노드는 2번 노드와 가중치 1로 연결되어 있다.
    또한, 3번 노드와는 가중치 3으로 연결되어 있다.
    2번 노드는 3번 노드와 가중치 3으로, 또 4번 노드와 가중치 6으로 연결되어 있다.
    (이하 생략)
    그러면, 인접 리스트는 노드의 숫자만큼을 생성하게 된다.
    list[1..5] 각각의 리스트 인덱스는 노드의 번호를 의미한다.
    이런식으로 인접 리스트가 생성되게 된다.
    오늘 소개할 코드에서는 인풋 1 2 1 에 대해서, 반대 방향 2 1 1 도 리스트에 추가한다.
  2. 이렇게 생성된 리스트를 가지고 최소 힙을 이용한다.
  3. 최소 힙에 최초에 집어넣을 리스트는 시작 노드인 1번 노드를 넣는다.
    1번 노드를 넣는다는 의미는 인접 리스트 list[1]의 모든 노드를 힙에 넣는다는 뜻이다.
  4. 최소 힙에서 루트 노드를 삭제하면서 값을 비교한다. 이 때, 배열 Nearst와 Distance를 이용한다.
    Nearst는 해당 인덱스에 대해서 어떤 노드와 연결되었는지를 담고 있을 배열이다.
    예를 들어 2번 노드는 1번 노드와 연결되어 있다고 하면, Nearst[2] = 1; 이 되게 된다.
    이 때, Distance[2]에는 1번 노드와 2번 노드 사이의 가중치 1을 담게 된다. (Distance[2] = 1;)
  5. 힙에서 값을 비교할 때, Nearst의 값을 확인한다.
    이 때, 일단 힙에서 삭제를 하고, 해당 인덱스의 Nearst 배열 값이 -1이 아니라면 간선을 추가해주는 방법을 선택한다.
    그리고 카운터를 1만큼 증가시켜 준다.
    (배열 Nearst는 -1로, Distance는 0으로 초기화를 한다. 코드에서는 n과 d로 표현되어 있다.)
    (카운터는 0으로 초기화를 한다.)
  6. 2번부터 5번까지의 과정을 계속해서 반복한다.
    그러면서, 카운터의 크기가 노드의 수만큼 되었을 때 루프를 종료한다.
    *계속 루프를 돌아도 상관은 없으나 효율성이 떨어지는 코드가 되게 된다.

위의 과정을 구현한 코드는 다음과 같다.

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

#pragma warning(disable:4996)

#define MAX_FILE_NAME 50
#define MAX_HEAP_SIZE 4096
#define TRUE          1
#define FALSE         0

typedef struct _LIST {
    int startVertex;
    int endVertex;
    int weight;
    struct _LIST *next;
} LIST;

typedef struct _HEAP_NODE {
    int startVertex;
    int endVertex;
    int w;
} HEAP_NODE;

typedef struct _HEAP {
    int size;
    struct _HEAP_NODE *heap;
} HEAP;


void list_Create(LIST *p, int start, int end, int w);
void heap_Initialize(HEAP *h);
void heap_Insert(HEAP *h, LIST *l);
void heap_Build(HEAP *h);
void heap_SiftDown(HEAP *h, int i);
void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src);
int heap_Delete(HEAP *h);


int main() {
    FILE *fp_in;
    char input[MAX_FILE_NAME];
    LIST *list;
    HEAP h;
    int numberOfVertices, numberOfEdges;
    int i, counter, totalWeight;
    int tmp_start, tmp_end, tmp_w;
    int x, y, z;
    int *n, *d;

    printf("Enter the FILE Name or Path => ");
    scanf("%s", input);

    fp_in = fopen(input, "r");
    if (fp_in == NULL) {
        fprintf(stderr, "FILE <%s> open error.\n", input);
        return -1;
    }

    fscanf(fp_in, "%d %d", &numberOfVertices, &numberOfEdges);

    list = (LIST *) malloc(sizeof(LIST) * (numberOfVertices + 1));
    if (list == NULL) {
        fprintf(stderr, "Memory allocation error: *list\n");
        return -1;
    }

    for (i = 1; i <= numberOfVertices; i++) {
        list[i].next = NULL;
        list[i].startVertex = i;
        list[i].endVertex = -1;
        list[i].weight = -1;
    }
    for (i = 1; i <= numberOfEdges; i++) {
        fscanf(fp_in, "%d %d %d", &x, &y, &z);
        list_Create(&list[x], x, y, z);
        list_Create(&list[y], y, x, z);
    }

    n = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (n == NULL) {
        fprintf(stderr, "Memory allocation error: *n\n");
        return -1;
    }
    d = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (d == NULL) {
        fprintf(stderr, "Memory allocation error: *d\n");
        return -1;
    }
    for (i = 1; i <= numberOfVertices; i++) {
        n[i] = -1;
        d[i] = 0;
    }

    heap_Initialize(&h);

    counter = 0;
    totalWeight = 0;
    while (TRUE) {
        if (counter == numberOfVertices) {
            break;
        }

        while (TRUE) {
            tmp_start = h.heap[1].startVertex;
            tmp_w = h.heap[1].w;
            tmp_end = heap_Delete(&h);
            if (n[tmp_end] == -1) // n[tmp_end] indicates -1: not select, else: selected
            {
                heap_Insert(&h, &list[tmp_end]);
                n[tmp_end] = tmp_start;
                d[tmp_end] = tmp_w;
                totalWeight += tmp_w;
                counter++;
                break;
            }
        }
    }

    printf("\n=====================================================\n");
    printf("Nearest : ");
    for (i = 2; i <= numberOfVertices; i++) {
        printf("%3d ", n[i]);
    }
    printf("\nDistance: ");
    for (i = 2; i <= numberOfVertices; i++) {
        printf("%3d ", d[i]);
    }
    printf("\n=====================================================\n");
    printf("Total Weight: %d\n\n\n", totalWeight);

    fclose(fp_in);
    free(list);
    free(d);
    free(n);
    free(h.heap);

    return 0;
}

void list_Create(LIST *p, int start, int end, int w) {
    LIST *tmp, *pointer;

    pointer = p;
    tmp = (LIST *) malloc(sizeof(LIST));
    if (tmp == NULL) {
        fprintf(stderr, "Memory allocation error: list_create()\n");
        return;
    }

    tmp->next = NULL;
    tmp->startVertex = start;
    tmp->endVertex = end;
    tmp->weight = w;

    while (TRUE) {
        if (pointer->next == NULL) {
            pointer->next = tmp;
            break;
        } else
            pointer = pointer->next;
    }
}

void heap_Initialize(HEAP *h) {
    h->heap = (HEAP_NODE *) malloc(sizeof(HEAP_NODE) * MAX_HEAP_SIZE);
    if (h->heap == NULL) {
        fprintf(stderr, "Memory allocation error: heap_initialize()\n");
        return;
    }

    h->size = 1;
    h->heap[1].startVertex = 1;
    h->heap[1].endVertex = 1;
    h->heap[1].w = 0;
}

void heap_Insert(HEAP *h, LIST *l) {
    LIST *tmp = l;

    while (TRUE) {
        if (tmp->weight != -1) {
            h->size++;
            h->heap[h->size].startVertex = tmp->startVertex;
            h->heap[h->size].endVertex = tmp->endVertex;
            h->heap[h->size].w = tmp->weight;
            heap_Build(h);

            if (tmp->next == NULL)
                break;
            tmp = tmp->next;
        } else
            tmp = tmp->next;
    }
}

void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src) {
    int tmp_start = dst->startVertex;
    int tmp_end = dst->endVertex;
    int tmp_w = dst->w;

    dst->startVertex = src->startVertex;
    dst->endVertex = src->endVertex;
    dst->w = src->w;
    src->startVertex = tmp_start;
    src->endVertex = tmp_end;
    src->w = tmp_w;
}

int heap_Delete(HEAP *h) {
    int min;

    min = h->heap[1].endVertex;
    heap_Swap(&h->heap[1], &h->heap[h->size]);
    h->size--;
    heap_Build(h);

    return min;
}

void heap_SiftDown(HEAP *h, int i) {
    int largerChild;
    HEAP_NODE siftKey;
    int parent = i;
    int found = FALSE;

    siftKey = h->heap[i];
    while ((2 * parent <= h->size) && !found) {
        if ((2 * parent < h->size) && (h->heap[2 * parent].w > h->heap[2 * parent + 1].w))
            largerChild = 2 * parent + 1;
        else
            largerChild = 2 * parent;

        if (siftKey.w > h->heap[largerChild].w) {
            h->heap[parent] = h->heap[largerChild];
            parent = largerChild;
        } else
            found = TRUE;
    }
    h->heap[parent] = siftKey;
}

void heap_Build(HEAP *h) {
    int i;

    for (i = h->size / 2; i >= 1; i--) {
        heap_SiftDown(h, i);
    }
}

인풋에 대한 결과는 다음과 같다.

5 7
1 2 1
1 3 3
2 3 3
2 4 6
3 4 4
3 5 5
4 5 5

댓글 남기기