최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘

최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘

프림 알고리즘(Prim's algorithm)

- 프림 알고리즘은 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다.

- 알고리즘이 동작되는 동안에, 트리에 연결되지 않은 정점들은 큐에 배정되어 있다.

- 각 정점들은 key 값을 가지고, 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택한다.

1. 동작 원리

(1) 각 정점들의 key 값과, 다른 정점을 가르키는(pre) 값을 초기화한다.

(2) 모든 정점들을 큐에 배정하고, 시작 위치의 key값을 0으로 초기화한다.

(3) 큐에 배정된 정점 중, key 값이 가장 작은 정점을 꺼낸다.

(4) 꺼내온 정점을 기준으로, 인접한 정점 중에 큐에 아직 배정되어 있고(=트리를 형성하지 않았고)

현재 정점에서의 이동 비용이 가장 작은 정점을 찾아 값을 갱신한다.

(5) 큐에서 모든 정점을 꺼낼 때까지 반복한다.

[ Fig. 1 ] process of Prim's algorithm, cite : introduction to algorithms 3/E

2. 함수 설명

prim( int) : 프림 알고리즘의 메인 부분으로, 동작월니 (1) (2) (4) (5)에 해당한다.

extract_min() : 삽입 정렬을 이용하여, 큐에 배정되어있는 정점 중, 키 값이 가장 작은 정점을

반환해준다.

3. 함수 구형

 

#include <stdio.h> #define MAX_VERT    20 #define INF         9999 #define UNDEF       -1 #define UNADJACENCY 0 #define STARTPOINT  0 typedef struct vertices{     int key;     int pre; }VT; typedef struct queue{     int front;     int v[MAX_VERT];     int rear; }QUEUE; int w[MAX_VERT][MAX_VERT]; VT v[MAX_VERT]; QUEUE Q; int extract_min( void); void enqueue( int); int queue_empty( void); int find_queue( int); void prim( int); int main( void) {     int t, tc;     int nv, ne;     int s, d, wt;     int i;     freopen("input.txt", "r", stdin);     // what is the number you want repeat?     scanf("%d", &tc);     for( t = 0 ; t < tc ; t ++)     {         // input the number of vertices and edges.         scanf("%d%d", &nv, &ne);         for( i = 0 ; i < ne ; i ++)         {             // input two vertices that you want to input the weight of the edge.             scanf("%d%d%d", &s, &d, &wt);             // we will get the undirected graph.             w[s-1][d-1] = wt;             w[d-1][s-1] = wt;         }         prim( nv);     }     return 0; } /*     prim( int)     it's MST algorithms.     it operates much like Dijkstra's algorithm.     At each step of the algorithm, the vertices in the tree     determine a cut of the graph. */ void prim( int nv) {     int i, u;     // initialize the vertices and add each them to the queue.     for( i = 0 ; i < nv ; i ++)     {         v[i].key    = INF;         v[i].pre    = UNDEF;         enqueue(i);     }     // set '0' vertex as the starting point     v[0].key    = STARTPOINT;     while( !queue_empty())     {         // get the vertex that has the minimum value of the key.         u   = extract_min();         for( i = 0 ; i < nv ; i ++)         {             // check the adjacency vertices             if( w[u][i] != UNADJACENCY)             {                 // find a route that has the lowest weight.                 if( find_queue(i) && (w[u][i] < v[i].key))                 {                     v[i].key    = w[u][i];                     v[i].pre    = u;                 }             }         }     }     // display the edges of the tree.     for( i = 1 ; i < nv ; i ++)     {         printf("%c - %c\n", 'a'+i, 'a'+v[i].pre);     } } /*     find_queue( int)     This function give back the element that you want to find. */ int find_queue( int v) {     int i;     for( i = Q.front ; i < Q.rear ; i ++)     {         if( Q.v[i]  == v)             return 1;     }     return 0; } /*     queue_empty(void)     examine whether the queue is empty. */ int queue_empty( void) {     return Q.front == Q.rear; } /*     enqueue( int)     after creating a new node, add it to the queue */ void enqueue( int v) {     Q.v[Q.rear++]   = v; } /*     extract_min( void)     this function give back the vertex that     has the minimum value of key in the queue. */ int extract_min( void) {     int i, j;     int key;     // insertion-sort     for( i = Q.front+1 ; i < Q.rear ; i ++)     {         key = Q.v[i];         j   = i;         while( (--j >= Q.front) && ( v[key].key < v[Q.v[j]].key))         {             Q.v[j+1]    = Q.v[j];         }         Q.v[j+1]    = key;     }     return Q.v[Q.front++]; }

 

4. 실행 결과

Fig. 1의 그림을 기준으로 알고리즘을 수행한 결과, 다음과 같은 선분이 연결되어

MST를 구성하였다.