크루스칼 알고리즘 (Kruskal Algorithm) with Union-Find 알고리즘

 

 

 

 

크루스칼 알고리즘 (Kruskal Algorithm)이란,

그래프의 최소 비용 신장 트리(Minimal Spanning Tree : MST)를 구하는 그리디 알고리즘이다.

그리디 알고리즘으로써 최적의 해답을 얻을 수 있다는 사실이 증명되어 있다.

 

기본 과정은 다음과 같다.

1. 그래프의 간선들을 가중치 오름차순으로 정렬한다.

2. 첫번째 간선부터(즉, 가중치가 가장 낮은 간선부터) 선택한다.

3. 선택했을 때, 현재의 MST 집합에 사이클을 형성하는지 여부를 판단한다.

4. 사이클을 형성하면 배제하고, 그렇지 않으면 MST 집합에 추가한다.

 

이 때, 사이클 형성 여부는 Union-Find 알고리즘을 이용한다.

 

Disjoint Set : 서로 중복되지 않는, 상호 배타적인 부분 집합들로 나눠진 원소들을 저장한 자료구조.

서로소 집합 자료구조.

Union-Find : Disjoint Set을 다루는 알고리즘. find와 merge라는 두 함수를 활용한다.

 

find : 원소가 속한 집합을 반환한다.

merge : 두 원소가 속한 집합을 하나로 합친다.

 

다음 예시에서 Disjoint Set은 배열을 활용해 트리 구조로 구성한다. 같은 집합에 속한 원소들은 같은 트리에 속하며, 이는 즉 root를 공유함을 뜻한다. 배열의 인덱스는 원소의 id를 의미하고, 인덱스에 따른 배열의 값은 트리에서 해당 원소의 부모 원소를 담고 있다. 트리의 root 원소의 경우 -1을 저장해둔다. 이 같은 자료구조를 활용하여 다음과 같이 구현된 find 함수는 인자로 주어진 원소 a가 속한 집합 트리의 root 원소의 id를 반환하게 된다.

 

int find(int a) {

  if (pt[a] < 0) {

    return a;

  }

  pt[a] = find(pt[a]);

  return pt[a];

}

 

같은 집합 트리에 속한 원소는 같은 root를 공유하므로 find의 결과값이 같을 것이고, 아니라면 다를 것이다. 이를 통해 두 원소가 같은 집합 트리에 속하는지 확인할 수 있다.

 

void merge(int a, int b) {

  a = find(a);

  b = find(b);

  if (a == b) {

    return;

  }

  pt[a] = b;

}

 

두 원소가 속한 집합을 하나로 합치는 작업은, 두 원소의 트리의 각각의 root 원소를 find를 통해 찾은 뒤에(같다면 이미 같은 집합에 속하므로 종료), 두 root 원소 사이에 부모 자식 관계를 만들어주면 된다.

 

다시 크루스칼 알고리즘으로 돌아와서, 수도 코드를 구하면 다음과 같다.

int result[] : MST 집합. 공집합으로 시작.

int E[] : 간선의 집합. 오름차순으로 정렬할 예정.

int pt[] : 간선의 disjoint set. -1로 초기화되어 있음.

int weight[] : 간선의 id에 따른 가중치.

int n : 간선의 개수.

 

수도 코드

kruskal(int result[], int E[], int pt[], int weight[], int n){

  sort(E, weight);

  for(int i = 0; i < n; i++){

    int cur = E[i];

    int root = -1;

    if(result.length == 0){

      result.add(cur);

      root = cur;

    } else{

      if(find(cur) != find(root){

        merge(cur, root);

        result.add(cur);

      }

    }

  }

}

 

시간 복잡도 : 간선들을 정렬하는 시간에 좌우된다. 그러므로 간선의 개수를 E라고 할 때, O(E log E)