[그래프] 최소 신장 트리(MST, minimum spanning tree) - 2

1. 문제정의

최소 신장 트리 ( Minimum Spanning Tree )란?

최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.

BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다.

MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다.

 

---

2. 문제 설계

Prim's 알고리즘Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후,그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다.

---

3. 구현

#include <stdio.h>
#include <limits.h>
#define V 9

//다음에 수행할 정점을 구함
int minD(int d[], bool mstSet[]){

   int min = INT_MAX, min_index;
   for (int v = 0; v < V; v++)

     if (mstSet[v] == false && d[v] < min)
         min = d[v], min_index = v;

   return min_index;
}

int primMST(int graph[V][V]){
     int parent[V]; // 스패닝트리 간선 정보를 담는 배열 ex. parent[i]와 i는 연결되어 있음.

     int d[V];   // Distance 정보 담는 배열
     bool mstSet[V];  // 수행됬음을 알려주는 배열

     int sum = 0;
     //초기화

     for (int i = 0; i < V; i++)
        d[i] = INT_MAX, mstSet[i] = false;

     // 시작점
     d[0] = 0;    

     parent[0] = -1; // 시작점의 부모 정점은 없음.
    //트리의 간선 수 = 정점 수 - 1

     for (int count = 0; count < V-1; count++){ 
        //다음에 사용할 정점을 구함

        int u = minD(d, mstSet);
        mstSet[u] = true;

        //D-value 갱신 및 스패닝 트리 정보 갱신
        for (int v = 0; v < V; v++)

          if (graph[u][v] && mstSet[v] == false && graph[u][v] <  d[v]){
     parent[v]  = u;

     d[v] = graph[u][v];
    }  

     }
  for (int i = 1; i < V; i++)

   sum += graph[i][parent[i]];
 return sum;

}
int main(){

   int graph[V][V] = {{0,4,0,0,0,0,0,8,0}, //수업시간에 예제로 사용한 그래프
                      {4,0,8,0,0,0,0,11,0},

                      {0,8,0,7,0,4,0,0,2},
                      {0,0,7,0,9,14,0,0,0},

                      {0,0,0,9,0,10,0,0,0},
   {0,0,4,14,10,0,2,0,0},

  {0,0,0,0,0,2,0,1,5},
  {8,11,0,0,0,0,1,0,7},

  {0,0,2,0,0,0,5,7,0},};
    int result = primMST(graph);

    printf("%d\n", result);
    return0; 

}

---

4. 분석

 Prim 알고리즘 정점크기의 D-value 배열을 정점의 개수만큼의 횟수로 갱신하기 때문에 Big-O는 O(V^2)이다. 일반적으로 O(n^2)은 n의 최대 크기가 5,000일 때, 1초안에 답을 낼 수 있다. 하지만 graph가 2차원 배열이므로 배열의 최대 크기를 넘을 수 없다. 따라서 제시된 코드는 각 언어의 2차원 배열 최대크기까지만 입력을 받을 수 있다.