자료구조 :: 그래프(5) Prim의 최소비용 신장트리

# Prim의 MST 알고리즘

Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법이다.
시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다. Prim의 방법은 앞단계에서 만들어진 신장트리 집합에
인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 N-1개의 간선을
가질 때 까지 계속 된다.

신장 트리 집합에 정점 {a,f}가 포함된 상태에서 인접 정점으로 {a,b}와 {f,e}가 있을 때 이 간선들의 가중치 값이
더 작은 정점 하나가 신장 트리에 추가된다. {a,b}가 27이고 {f,e}가 29일때, 신장트리 집합은 {a,f,b}가 된다.

Prim의 알고리즘은 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 복잡도는 O(n²)이다.
Kruskal의 알고리즘은 복잡도가 O(elog₂e)이므로 희박한 그래프를 대상으로 할 경우에는 Kruskal의 알고리즘이
적합하고, 밀집한 그래프의 경우에는 Prim의 알고리즘이 유리하다고 할 수 있다.

Prim.cpp

#include <stdio.h> 
#defineTRUE1
#defineFALSE0

#define VERTICES 7
#define INF 1000L

int adj_mat[VERTICES][VERTICES]={ 
{ 0, 29, INF, INF, INF, 10, INF }, 
{ 29,  0, 16, INF, INF, INF, 15 },  
{ INF, 16, 0, 12, INF, INF, INF }, 
{ INF, INF, 12, 0, 22, INF, 18 }, 
{ INF, INF, INF, 22, 0, 27, 25 }, 
{ 10, INF, INF, INF, 27, 0, INF }, 
{ INF, 15, INF, 18, 25, INF, 0 }}; 

int selected[VERTICES]; 
int dist[VERTICES]; 

// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n) 
{ 
int v,i; 

for (i = 0; i <n; i++) 
    { 
if (!selected[i]) 
        {  
            v = i;  
break; 
        } 
    } 
// 선택하지 않은 간선들 중 최소 가중치값을 갖는 정점을 찾는다.
for (i = 0; i < n; i++) 
    { 
if( !selected[i] && (dist[i] < dist[v]))  
            v = i; 
    } 

return (v); 
} 

// 
void prim(int s, int n) 
{ 
int i, u, v; 

for(u=0;u<n;u++) 
        dist[u]=INF; 

    dist[s]=0; 
for(i=0;i<n;i++) 
    { 
        u = get_min_vertex(n); 
        selected[u]=TRUE; // 지나간 경로 체크

if( dist[u] == INF ) return; 

        printf("%d\n", u); 

for( v=0; v<n; v++) 
        { 
if( adj_mat[u][v]!= INF) 
            { 
if( !selected[v] && adj_mat[u][v]< dist[v] )  
                    dist[v] = adj_mat[u][v]; // 간선의 거리를 확정
            } 
        } 
    } 
} 

//
void main() 
{ 
    prim(0, VERTICES); 
}