[ Algorithm ] Prim's Algorithm 이란?

 

Prim's Algorithm 이란?

   최소 비용 신장 트리를 구하는 알고리즘 중 하나로, 가중치를 가지는 그래프에서, 가장 작은 가중치를 가지는 간선(Edge)를 시작으로

   인접한 정점과 연결된 Edge들 중에서, 가장 작은 가중치를 가지는 간선(Edge)들을 선택하는 방식이다.

 

   Prim 알고리즘은, 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복됩니다. 그러므로 시간복잡도는 O(N*N) 입니다.

Prim's Algorithm 동작

   1. 시작 단계에서, 시작 정점만을 MST(최소 비용 신장 트리) 집합에 포함합니다.

   2. MST(최소 비용 신장 트리) 집합에 포함된 정점들에 인접한 정점과 최소 간선으로 연결할 수 있는 정점을 집합에 넣어줍니다.

   3. 이러한 과정을 간선이 N-1개, 즉 Cycle이 발생시키지 않게 반복합니다.

Prim's Algorithm의 구체적인 원리

   1. 정점(Vertex) 선택을 기반으로 하는 알고리즘

   2. 이전 단계에서 만들어진 신장 트리를 확장  

Prim Algorithm Pseudo code

T = {}
TV = {0};
while (T는 n-1개의 edge보다, 적게 edge를 포함하고 있어야 합니다.)
{
	만약 Vertex가 TV에 포함되고, 인접한 Vertex를 TV에 포함하고 있지 않음을 가정하자.
    
    if (edge가 없다면) {
    	break;
    }
    add v to TV;		// 인접한 Vertex를 추가합니다.
    add (u, v) to T;		// 최소의 신장트리를 가진 edge도 추가합니다.
}

if (T가 n-1개의 edge보다 적게 포함하고 있다면,) {
	print("no spanning Tree");
}

Prim's Algorithm code with C/C++

// Prim's Algorithm in C

#include<stdio.h>
#include<stdbool.h> 

#define INF 9999999
#define V 5

int G[V][V] = {
  {0, 9, 75, 0, 0},
  {9, 0, 95, 19, 42},
  {75, 95, 0, 51, 66},
  {0, 19, 51, 0, 31},
  {0, 42, 66, 31, 0}};

int main() {
  int no_edge;  // number of edge

  int selected[V];
  memset(selected, false, sizeof(selected));
  
  no_edge = 0;

  selected[0] = true;

  int x;  //  row number
  int y;  //  col number

  printf("Edge : Weight\n");

  while (no_edge < V - 1) {

    int min = INF;
    x = 0;
    y = 0;

    for (int i = 0; i < V; i++) {
      if (selected[i]) {
        for (int j = 0; j < V; j++) {
          if (!selected[j] && G[i][j]) {  
            if (min > G[i][j]) {
              min = G[i][j];
              x = i;
              y = j;
            }
          }
        }
      }
    }
    printf("%d - %d : %d\n", x, y, G[x][y]);
    selected[y] = true;
    no_edge++;
  }

  return 0;
}

Author's GitHub

https://github.com/kalelpark