C언어 C++, 알고리즘, 임베디드

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

프로그래밍 언어들/알고리즘

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

이용전 2016. 10. 19. 02:58

최소신장트리(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과는 연결 선분이 약간 다르지만, 선분 내에 동일한 가중치가 있기 때문에

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

 

 

2 Comments
댓글쓰기 폼