[Algorithm] Kruskal's Algorithm

개요

최소 신장트리를 구하는 알고리즘. 비용이 낮은 edge부터 편입시키는 방법이다.

High-level psudo code

Set<edge> F = {};                                                                     // 최소신장트리
create disjoint subsets of V, one for each vertex and containing only that vertex;    // 모든 정점마다 해당 점만 존재하는 부분집합을 생성한다.
sort the edges in E in nondecreasing order;                                           // 모든 Edge를 비용 오름차순으로 정렬한다.

While (the instance is not solved)
{
    select next edge;                                        // 가장 비용이 낮은 edge를 선택된다.
    if (the edge connects 2 vertices in disjoint subsets)    // 두 edge가 연결된 부분집합이 서로소집합이라면
    {
        merge the subsets;                                   // 두 집합을 합친다.
        add the edge to F;                                   // 해당 edge는 최소신장트리에 포함된다.
    }
    if (all the subsets are merged)                          // 모든 부분집합이 합쳐졌다면
        the instance is solved;                              // 문제는 해결되었다.

}

서로소 집합 추상 데이터 타입 (disjoint set abstract data type)

해당 집합의 부모를 가리키는 set_pointer를 사용하면 두 집합이 서로소 집합인지 알수 있다.

Kruskal's Algorithm

- Create-Sets(number n): n개의 서로소 집합을 초기화
- p = Find-set(index i) : vertex i가 포함된 set_pointer p를 넘겨줌
- Union(set_pointer p, q) : 두 집합 p, q를 합병
- Equal(set_pointer p, q) : 두 집합이 동일한 집합인지 비교

// n : 정점의 개수
// m : Edge의 개수
// E : Graph의 모든 Edge들
// F : 반환용 최소신장트리
void kruskal (int n, int m, set_of_edges E, set_of_edges& F) 
{
    index i, j;
    set_pointer p, q;
    edge e; 

    Sort the m edges in E by weight in nondecreasing order; // Edge들을 오름차순으로 정렬한다.
    F = {};         // 최소 신장 트리
    Create-Sets(n); // n개의 독립된 집합을 생성한다.

    while (number of edges in F is less than n-1) // F에 정점개수-1만큼 채워넣을때까지 반복한다.
    {
        e = edges with least weight no yet considered; // 최소비용 edge
        i,j = indices of vertieces connected by e;     // e의 양 끝점
        p = Find-set(i); // i가 포함된 집합
        q = Find-set(j); // j가 포함된 집합
        if (!Equal(p,q)) // 만약 p, q가 같지 않다면
        {
            Union(p,q);  // p, q를 합쳐준다.
            add e to F;
        }
    }
}

Complexity

- 단위연산 : 비교문
- 입력크기 : 정점의 수 n, 이음선의 수 m
- Time-complexity : $O(m log m)$ (정렬 $O(m log m)$ + 반복문 $O(m log n)$ + 집합초기화 $O(n)$)
- Worst-case(m, n) : $O(n^2 log n)$ (모든 정점이 다른 모든 정점과 연결되는 경우)