[Algorithm] # Kruskal Algorithm

kruskal 알고리즘은 최소의 비용으로 간선을 연결해 정점들을 모두 연결시키는 알고리즘입니다. 최소 신장 비용 트리를 구현하는 것이죠. 사용 예로는 네트워크, 전화선을 연결할때 사용합니다.

Concept

kruskal 알고리즘은 아래의 조건들을 만족하여 구현합니다.

• 간선들을 최소비용으로 오름차순하여 정렬합니다.
• 최소 비용의 간선들을 하나씩 선택하는데, 중요한건 사이클이 생기지 않도록 해야 합니다. 사이클이 발생한다는 소리는 이미 최소비용이 아니라는 의미이기도 하기 때문이죠.

사이클 validation

위에서 사이클을 발생시키지 않아야 한다고 했는데, 이를 어떤 식으로 검증해야할까요? 이전에 정리했던 Union-Find 알고리즘을 활용하면 됩니다. 즉, 간석을 선택하고 양 끝에 연결된 정점이 같은 집합이라면 사이클이 발생할 수 밖에 없습니다.

• Union-Find 알고리즘을 활용해, 같은 집합의 간선을 배제합니다.

코드

실제 구현 코드는 아래와 같습니다.

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

#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 100
#define INF 1000

int parent[MAX_VERTICES];

void set_init(int n) {
  for (int i = 0; i < n; i++) {
    parent[i] = -1;
  }
}

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 n;
  struct Edge edges[2 * MAX_VERTICES];
} GraphType;

void init_graph(GraphType *g) {
  g->n = 0;
  for (int i = 0; i < 2 * MAX_VERTICES; i++) {
    g->edges[i].start = 0;
    g->edges[i].end = 0;
    g->edges[i].weight = INF;
  }
}

void insert_edge(GraphType *g, int start, int end, int weight) {
  g->edges[g->n].start = start;
  g->edges[g->n].end = end;
  g->edges[g->n].weight = weight;
  g->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;
}

void kruskal(GraphType *g) {
  int edge_accepted = 0;
  int uset, vset;
  struct Edge e;

  set_init(g->n);
  qsort(g->edges, g->n, sizeof(struct Edge), compare);

  printf("kruskal algorithm\n");
  int i = 0;
  while(edge_accepted < (g->n - 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_accepted++;
      set_union(uset, vset);
    }
    i++;
  }
}

int main(void) {
  GraphType *g = (GraphType*)malloc(sizeof(GraphType));
  init_graph(g);

  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;
}