Kruskal's Algoritm

 

Prim's Algorithm

저번에는 Prim's Algoritm을 이용해서 graph에서 minimum spanning tree를 구하는 방법을 알아봤다.

Kruskal's Algorithm역시 graph에서 minimum spanning tree를 구하는 알고리즘이지만,

접근 방식에서 약간의 차이가 있다.

 

Prim 알고리즘은 vertex를 중심으로 설계했다면,

Kruskal 알고리즘은 edge 중심의 설계 방식을 채택했다.

 

Kruskal's Algorithm

이 알고리즘의 동작 과정을 살펴보자.

위 집합은 여러개의 부분집합을 1개의 집합으로 통합하는 과정에서 minimum spanning tree를 구성하게 되는데,

집합을 통합하는 방식은 다음과 같다.

 

1. edge들을 weight의 오름차순으로 정렬한다.
2. weight가 가장 작은 edge로 연결된 부분집합을 merge한다.
   단, 해당 edge를 추가할 때 cycle이 만들어지는 경우에는 해당 edge를 추가하지 않는다.
3. 집합이 1개만 남을 때까지 반복한다.

 

위 알고리즘을 의사코드로 구현해보자.

구현하기에 앞서 몇 가지 규칙을 정하자.

 

우선, 집합관계는 아래와 같은 배열을 사용해서 관리한다.

U[i]는 Vi가 가리키고 있는 vertex의 인덱스를 저장하고,

연결되어 있는 vertices는 집합이라고 정의한다.

탐색은 자식부터 연쇄적으로 부모로 올라가며, 결국 root node는 본인을 가리키는 구조가 된다.

 

그리고 아래와 같은 함수를 사용한다.

initial(n): 서로소 집합을 초기화한다. (각 집합에는 1~n의 인덱스를 갖는 vertex 하나만 들어간다)
p = find(i): Vi가 들어가있는 집합을 찾아 p가 이 집합을 가리키도록 한다.
merge(p, q): 두 집합 p, q를 합친다.
equal(p, q): p, q가 같은 집합을 가리키면 true를 반환한다.

 

- initial(n)

for (i=1; i<=n; i++) {
    U[i] = i;
}

 

-  p = find(i)

Vi가 속한 집합을 구성하는 트리의 root node의 인덱스를 반환해 p에 저장한다.

index search = i;
while (U[search] != search) {
    search = U[search];
}
return search;

 

- merge(p, q)

p, q를 합치는데, depth가 작은 tree(집합)을 자식으로 삼는다.

만약 p, q모두 depth가 같다면 q를 자식으로 삼는다.

 

이제 의사코드를 살펴보자.

// n: # of vertices
// m: # of edges
public static setOfEdge kruskal(int n, int m, setOfEdge E) {
    setPointer p, q; // index p, q로 해도 될 듯..?
    setOfEdge F = {};
    
    집합 E에 들어있는 m개의 edge를 오름차순으로 정렬;
    initial(n);
    
    // n개의 vertices가 모두 연결되면 n-1개의 edge로 연결된 셈.
    while (|F| < n-1) {
        Edge e = 고려하지 않은 edge 중 가장 작은 weight를 갖는 edge;
        index i, j = e로 연결된 vertces의 indices;
        
        p = find(i);
        q = find(j);
        // 같은지 검사하는 이유는,
        // 같은 집합에 들어있는 두 vertices를 연결하면 cycle이 생기기 때문.
        if (!equal(p, q)) {
            merge(p, q);
            add e to F;
        }
    }
    
    return F;
}

위 알고리즘의 시간 복잡도는 아래와 같이 구할 수 있다.

 

1. edge 정렬: MergeSort. Θ(m lg m)
2. initial: Θ(n)
3. while loop: 서로소 집합 구현. Θ(m lg m)

 

즉 Θ(m lg m)의 시간 복잡도를 갖고,

vertex가 n개 있을 때, edge의 수 m는 아래와 같은 관계를 갖는다.

$$ n-1 \leq m \leq n(n-1)/2 $$

따라서 worst case에는 Θ(n^2 lg n)의 시간 복잡도를 갖는다.

 

Optimality

그렇다면, Kruskal 알고리즘 역시 Prim과 마찬가지로 최적해를 도출해줄까?

이를 증명하기 위해 이전과 마찬가지로 promising 개념을 사용하여 점화식을 만들자.

 

1. F = {}는 promising 하다. (자명)
2. 몇 번의 과정을 거친 F가 promising 하다고 가정한다.
3. 다음 루프의 F (즉 F union {e})가 promising 한 것을 증명한다.
   (여기서 e는 F에 포함되지 않으며, F union {e}가 cycle이 없도록 하는 edge 중 weight가 가장 작은 edge)

 

여기서 위 점화식이 참이라면 아래와 같은 관계가 성립된다.

F는 promising하기 때문에, F를 부분집합으로 갖고있는 F'가 존재할 것이고,
F'역시 promising, 즉 minimum spanning tree이다.

 

이 때 Prim과 마찬가지로 두 가지 경우로 나뉘며 두 경우 모두 증명해야 한다.

 

- Case 1: F'가 e를 포함하는 경우

이 경우에는 F union {e}가 F'의 부분집합 이므로 promising 하다는 것이 자명하다.

 

- Case 2: F'가 e를 포함하지 않는 경우

이 경우에는 F union {e}는 F'의 부분집합이 아니다.

하지만, F' union {e'} - {e}의 부분집합이긴 하다.

 

Prim의 Optimality를 증명하는 과정과 마찬가지인 이유로

F union {e}가 F' union {e'} - {e}의 부분집합이기 때문에

F union {e}는 promising하다.

 

Prim vs Kruskal

Prim의 시간 복잡도는 Θ(n^2)

Kruskal의 시간 복잡도는 worst case에서 Θ(n^2 lg n) (best에선 Θ(n lg n)까지 내려감)

 

따라서 m(edge의 개수)이 n-1에 가까울 수록,

즉, graph가 한산할수록 Kruskal을 사용하는 것이 더 효율적이고,

m이 n(n-1)/2에 가까울 수록,

즉, graph가 빽빽할수록 Prim을 사용하는 것이 더 효율적이다.