최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘

최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘

신장트리란?

- 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것

최소 신장 트리(MST : Minimum Spanning Trees)란?

- 최소한의 비용(가중치)로 신장 트리를 형성하는 것

크루스칼(Kruskal) 알고리즘

- 최소 신장 트리를 형성하기 위한 알고리즘

- Disjoint-set을 사용한다.

 * 대표 원소(representitive)를 통해 각 set을 분별하는 방식.

 * 이에 대해서는 차 후에 자세하게 다루겠다.

1. 동작원리

(1) 모든 정점들(vertices)을 독립적인 원소(set)로 만든다.

(2) 모든 선분들(edges)을 가중치를 기준으로 정렬한다.

(3) 가중치가 작은 선분부터 선분을 연결하는 두 정점들을 비교한다.

(4) 두 정점의 대표정점을 확인한다.

(5) 대표 정점이 다를 경우 두 정점을 연결한다.( 사이클 형성 방지 )

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

 

3. 함수 구현

 

#include <stdio.h> #define MAX_VER     15 #define MAX_EDGE    30 typedef struct edge{     int s,d;     int w; }EDGE; struct vertices{     int p;     int rank; }vt[MAX_VER]; EDGE e[MAX_EDGE]; void mst_kruskal( int, int); void make_set( int); void connect( int, int); int find_set( int); void sort_edge( int); void max_heapify( int, int); void build_max_heap( int); int main( void) {     int t, tc;     int nv, ne;     int i;     int s, d;     freopen("input.txt", "r", stdin);     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 ++)         {             scanf("%d%d", &s, &d);             e[i].s  = s - 1;             e[i].d  = d - 1;                         scanf("%d", &e[i].w);         }         mst_kruskal( nv, ne);     }     return 0; } /*     make_set()     create a new set whose only member is itself. */ void make_set( int v) {     vt[v].p     = v;     vt[v].rank  = 0; } /*     find_set()     returns a pointer to the representative of the set. */ int find_set( int v) {     if( vt[v].p != v)     {         vt[v].p = find_set( vt[v].p);     }         return vt[v].p; } /*     connect()     unites the dynamic sets that contain two elements. */ void connect( int v, int u) {     v   = find_set( v);     u   = find_set( u);     // compare V with U.     if( vt[v].rank > vt[u].rank)     {         vt[u].p = v;     }     else     {         vt[v].p = u;         // if v has the equal number of vertices with u.         if( vt[v].rank == vt[u].rank)         {             vt[u].rank = vt[u].rank + 1;         }     } } /*     mst_kruskal()     it uses disjoint-set and finds a safe edge. */ void mst_kruskal( int nv, int ne) {     int i;     int total   = 0;     for( i = 0 ; i < nv ; i ++)     {         // create a new set whose only member is itself.         make_set(i);     }     // sort the edges.     sort_edge( ne);     for( i = 0  ; i < ne ; i ++)     {         // examine whether two representative is not similar each other.         if( find_set( e[i].s) != find_set( e[i].d))         {             // unites the dynamic sets that contain two elements.             connect( e[i].s, e[i].d);             total = total + e[i].w;             printf("(%c, %c), total weight : %d\n", e[i].s+97, e[i].d+97, total);         }     } } /*     sort_edge()     sort the edges by heap sort */ void sort_edge( int ne) {     EDGE temp;     int i;     build_max_heap( --ne);     for( i = ne ; i > 0 ; i --)     {         temp    = e[i];         e[i]    = e[0];         e[0]    = temp;         max_heapify( 0, i);     } } /*     max_heapify()     maintain the characteristic of the heap. */ void max_heapify( int index, int size) {     EDGE temp;     int left    = index * 2 + 1;     int right   = index * 2 + 2;     int largest = index;     if( left < size && e[left].w > e[largest].w)     {         largest = left;     }         if( right < size && e[right].w > e[largest].w)     {         largest = right;     }     if( largest != index)     {         temp        = e[largest];         e[largest]  = e[index];         e[index]    = temp;         max_heapify( largest, size);     } } /*     build_max_heap()     make the max heap */ void build_max_heap( int ne) {     int i;     for(i = ne/2 ; i >= 0 ; i--)     {         max_heapify( i, ne);     } }

 

4. 실행 결과

Fig. 1의 기준으로 구현한 실행 결과는 다음과 같다.

입력 파일은 다음을 사용하도록 한다. ( 프로젝트 내 소스코드 파일이 있는 디렉토리에 첨부하면 된다. )

input.txt

 

연결된 정점과, 누적 가중치를 출력하도록 구현하였다.

* Fig. 1과는 연결 선분이 약간 다르지만, 선분 내에 동일한 가중치가 있기 때문에

최종 누적 가중치는 동일하다.