Prim's Minimum Spanning Tree (MST)

개요 

• MST는 graph의 vertex들을 최소 비용으로 연결한 tree이다. 
• Prim의 알고리즘도 Kruskal의 알고리즘과 마찬가지로 greedy 알고리즘이다. 그리고 같은 greedy 알고리즘인 Dijkstra와 알고리즘이 거의 유사하다.

방법

• 두 개의 set을 유지한다. 첫 째는 이미 MST에 속한 vertex들, 두번 째는 여기에 포함되지 않은 녀석들. (즉, 두 set은 disjoint subset이다)
• 그래서 알고리즘은 두 set간의 모든 edge 중에서 가장 짧은 녀석을 선택하는 것이다. 선택된 edge는 다시 MST에 포함된다. 
• 그렇다면 두 set간의 edge는 어떻게 알 수 있나? 그것은 edge의 한쪽 vertex가 MST에 속하고 나머지 한쪽 vertex는 포함되지 않은 set에 있으면 된다. 

1) mstSet을 만든다. 여기에 포함되는 vertex는 MST에 이미 포함된 것들이다. 초기에는 당연히 empty set이다. 2) 그래프의 모든 vertex에 key를 대입한다. 초기값은 INFINITE이다. 0를 먼저 선택한다. 3) mstSet이 모든 vertex를 포함할 때까지 a) 포함되지 않는 node set에 있는 녀석들 중 최소 key를 가진 녀석 u를 선택한다. b) u를 mstSet에 포함시킨다. c) u의 모든 이웃 vertex들 (adjacent vertices)의 key 값을 update한다. 기존key값 보다 u-v edge값이 더 작으면 key값을 u-v edge값으로 바꾼다.

예제

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

 

• 모든 vertex의 key값은 INFINITE로 만든 뒤, 최초에 0을 mstSet에 집어넣는다. 그리고 0의 key값을 0으로 한다. 

 

• 그런 다음, 0의 모든 이웃 노드들에 대해서 key 값을 갱신해주는데 기존에 가지고 있던 값보다 0과의 edge weight값이 작다면 그것으로 update한다. 여기서는 1과 7의 key값이 각각 4, 8로 갱신되었다.  

 

• 가장 작은 key값을 가진 vertex를 선택하는데 여기서는 vertex 1 이다. 그리고 1의 이웃 노드 2의 key값을 8로 update한다.  

 

• 가장 작은 key값을 가진 vertex가 2와 7인데 뭘 골라도 상관없으나 7을 선택하는 것으로 하겠다. 그리고 7의 이웃 노드 6과 8의 key값을 각각 1, 7로 update한다. 

 

• 가장 작은 key값을 가진 vertex가 6을 선택하고 6의 이웃 노드 5과 8의 key값을 각각 2, 6로 update한다. 

 

• 이와 같이 진행하면 결국 위와 같은 MST를 얻을 수 있다. 

Code

#include <stdio.h>
#include <limits.h>
  
// Number of vertices in the graph
#define V 5
  
// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int minKey(int key[], bool mstSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
  
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
  
    return min_index;
}
  
// A utility function to print the constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
    printf("Edge   Weight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}
  
// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
    int parent[V]; // Array to store constructed MST
    int key[V];   // Key values used to pick minimum weight edge in cut
    bool mstSet[V];  // To represent set of vertices not yet included in MST
  
    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
  
    // Always include first 1st vertex in MST.
    key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
    parent[0] = -1; // First node is always root of MST 
  
    // The MST will have V vertices
    for (int count = 0; count < V-1; count++)
    {
        // Pick thd minimum key vertex from the set of vertices
        // not yet included in MST
        int u = minKey(key, mstSet);
  
        // Add the picked vertex to the MST Set
        mstSet[u] = true;
  
        // Update key value and parent index of the adjacent vertices of
        // the picked vertex. Consider only those vertices which are not yet
        // included in MST
        for (int v = 0; v < V; v++)
  
            // graph[u][v] is non zero only for adjacent vertices of m
            // mstSet[v] is false for vertices not yet included in MST
            // Update the key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
                parent[v]  = u, key[v] = graph[u][v];
    }
  
    // print the constructed MST
    printMST(parent, V, graph);
}
  
  
// driver program to test above function
int main()
{
   /* Let us create the following graph
          2    3
      (0)--(1)--(2)
       |   / \   |
      6| 8/   \5 |7
       | /     \ |
      (3)-------(4)
            9          */
   int graph[V][V] = {{0, 2, 0, 6, 0},
                        {2, 0, 3, 8, 5},
                        {0, 3, 0, 0, 7},
                        {6, 8, 0, 0, 9},
                        {0, 5, 7, 9, 0},
                       };
  
    // Print the solution
    primMST(graph);
  
    return 0;
}

• 출력값이다.

Edge   Weight 0 - 1    2 1 - 2    3 0 - 3    6 1 - 4    5

• Time complexity는 O(V²)이다. 모든 노드에 대해서 이웃 노드들의 key값을 모두 갱신하기 때문이다. 만일 binary heap을 사용할 경우 O(E logV)로 줄일 수 있다.