Kruskal's Minimum Spanning Tree (MST)

개요 

• Minimum Spanning Tree (MST)는 graph의 vertex들을 최소 비용으로 연결한 tree이다. 
• Kruskal의 알고리즘도 Prim의 알고리즘과 마찬가지로 greedy 알고리즘이다.

방법

• MST는 (vertex 개수 – 1)만큼의 edge로 구성되어 있다. 따라서 가장 작은 edge들을 (vertex 개수 – 1)만큼 선택하면 MST가 된다. 단 선택된 것들이 cycle을 이루지만 않으면 된다. 
• 이를 정리하면 아래와 같다. 

1) Edge들을 크기에 따라 오름차순 (non-decreasing order)으로 정렬한다. 2) 남아 있는 것들 중 크기가 가장 작은 edge를 선택하여 그것이 이미 MST set에 포함된 edge들과 cycle을 이루는지 확인한다. Cycle을 이루지 않으면 MST에 포함시킨다. 3) 두 번째 단계를 edge가 (vertex개수 – 1)만큼 선택될 때까지 반복한다.

• 문제는 두 번째 단계에서 cycle을 이루는지 어떻게 체크하냐는 것이다. 이를 위해 Union-Find algorithm을 사용한다. 

예제

• 아래의 그래프를 예로 들어 보자.  

• Edge들을 sorting하면 아래와 같이 된다. 

Weight   Src    Dest 1         7      6 2         8      2 2         6      5 4         0      1 4         2      5 6         8      6 7         2      3 7         7      8 8         0      7 8         1      2 9         3      4 10        5      4 11        1      7 14        3      5

• 이제 값이 작은 순서대로 선택해보자
• Edge 7-6 선택: Cycle이 없으니까 포함시킨다.

• Edge 8-2 선택: Cycle이 없으니까 포함시킨다.

• Edge 6-5 선택: Cycle이 없으니까 포함시킨다.

• Edge 0-1을 선택한다. Cycle이 없으니까 포함시킨다.

• Edge 2-5을 선택한다. Cycle이 없으니까 포함시킨다.

• Edge 8-6을 선택한다. Cycle이 생기므로 버린다.
• Edge 2-3 선택: Cycle이 없으니까 포함시킨다.

• Edge 7-8 선택: Cycle이 생기므로 버린다.
• Edge 0-7 선택: Cycle이 없으니까 포함시킨다.

• Edge 1-2 선택: Cycle이 생기므로 버린다.
• Edge 3-4 선택: Cycle이 없으니까 포함시킨다.

• 이제 V-1개의 edge가 선택되었기 때문에 알고리즘을 종료한다. 

Code

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int src;
    int dst;
    int weight;
} Edge;
 
typedef struct {
    int V; // Number of vertices
    int E; // Number of edges
    Edge* edge; // graph is represented as an array of edges
} Graph;
 
typedef struct {
    int parent;
    int rank;
} Subset;
 
// find the root of the specified element's subset
// (uses Path Compression)
int findRoot(Subset subsets[], int i)
{
    // find root and make root as parent of i
    if (subsets[i].parent != i)
        subsets[i].parent = findRoot(subsets, subsets[i].parent);
    return subsets[i].parent;
}
 
// do union of two subsets (uses Union by Rank)
void doUnion(Subset subsets[], int x, int y)
{
    int xRoot = findRoot(subsets, x);
    int yRoot = findRoot(subsets, y);
 
    // attach smaller rank tree under root of high rank tree
    if (subsets[xRoot].rank < subsets[yRoot].rank)
        subsets[xRoot].parent = yRoot;
    else if (subsets[xRoot].rank > subsets[yRoot].rank)
        subsets[yRoot].parent = xRoot;
 
    // if ranks are same, then make one as root and increment
    // its rank by one
    else {
        subsets[yRoot].parent = xRoot;
        subsets[xRoot].rank++;
    }
}
 
// Comparing funciton for qsort()
int myComp(const void* a, const void* b)
{
    return ((Edge*)a)->weight > ((Edge*)b)->weight;
}
 
// A utility function to print the constructed MST stored in the edge array
int printMST(Edge edge[], int E)
{
    printf("Edge   Weight\n");
    for (int i = 0; i < E; i++)
        printf("%d - %d    %d \n", edge[i].src, edge[i].dst, edge[i].weight);
}
 
void kruskalMST(Graph* graph)
{
    int V = graph->V;
    Edge* result = (Edge*)malloc(V * sizeof(Edge));
 
    // Step 1: Sort all the edges in non-decreasing order of their weight
    // If we are not allowed to change the given graph, 
    // we can create a copy of array of edges
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
 
    Subset* subsets = (Subset*)malloc(V * sizeof(Subset));
 
    // initialize all subsets as single element sets
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    // Number of edges to be taken is equal to V - 1
    int i = 0;
    int e = 0;
    while (e < V - 1) {
        // Step 2: Pick the smallest edge. 
        Edge smallestEdge = graph->edge[i++];
        int x = findRoot(subsets, smallestEdge.src);
        int y = findRoot(subsets, smallestEdge.dst);
 
        // if including this edge does't cause cycle, include it in result
        if (x != y) {
            result[e++] = smallestEdge;
            doUnion(subsets, x, y);
        }
    }
 
    // print the constructed MST
    printMST(result, e);
}
 
int main()
{
    /* Let us create following weighted graph
        10
    0--------1
    |  \     |
   6|   5\   |15
    |      \ |
    2--------3
        4       */
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = 4;
    graph->E = 5;
    graph->edge = (Edge*)malloc(sizeof(Edge) * graph->E);
 
    // add edge 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dst = 1;
    graph->edge[0].weight = 10;
 
    // add edge 0-2
    graph->edge[1].src = 0;
    graph->edge[1].dst = 2;
    graph->edge[1].weight = 6;
 
    // add edge 0-3
    graph->edge[2].src = 0;
    graph->edge[2].dst = 3;
    graph->edge[2].weight = 5;
 
    // add edge 1-3
    graph->edge[3].src = 1;
    graph->edge[3].dst = 3;
    graph->edge[3].weight = 15;
 
    // add edge 2-3
    graph->edge[4].src = 2;
    graph->edge[4].dst = 3;
    graph->edge[4].weight = 4;
 
    kruskalMST(graph);
 
    return 0;
} 

• edge를 weight를 기준으로 오름차순으로 정렬하는 것은 stdlib의 qsort를 사용하였다. (라인 73) 물론 직접 구현해도 된다. 
• 라인 89 ~ 96에서는 정렬된 edge 배열에서 가장 작은 순서대로 선택을 해서 그것이 cycle을 이루는 지 검사한다. 이때 사용하는 findRoot()와 doUnion()은 Union-Find 알고리즘을 사용하였다. findRoot() 메소드를 통해 edge의 양쪽, 그러니까 src와 dst가 같은 subset의 root를 가지는지 체크하고, 다르다면 결과에 넣고 같다면 cycle을 이루는 것이니까 넣지 않는다. 그리고 이때에는 doUnion() 메소드를 사용하여 같은 src와 dst를 같은 subset으로 만든다. 
• Time Complexity는 O(ElogE) 또는 O(VlogV)이다. Edge sorting이 O(ElogE)이고 union-find는 O(logV)이다. 따라서 전체는 O(VlogV + VlogE)가 된다. 사실 E는 최대 V²이고 log E는 2logV이니까 그냥 O(ElogE) 또는 O(VlogV)라고 봐도 무방하다.