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

# 신장 트리(spanning tree)

신장트리란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이
연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히
(n-1)개의 간선으로 연결하게 된다.


# 최소비용 신장트리(minimum spanning tree : MST)

최소비용 신장트리는 가중치를 간선에 할당한 그래프인 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과
비용으로 연결하는데 필요하다. 최소비용 신장트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장
트리를 말한다.

최소비용 신장트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이
알고리즘들은 최소비용 신장트리가 간선의 가중치의 합이 최서이어야 하고, 반드시 (n-1)개의 간선만 사용하며,
사이클이 포함되어서는 안된다는 조건들을 적절히 이용하고 있다.


# Kruskal 의 MST 알고리즘

Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법이란 결정을 해야 할 때마다
그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다.

Kruskal 알고리즘을 이용하여 최소 비용 신장 트리를 만드는 방법은 간선들을 가중치의 오름차순으로 정렬하고
가장 낮은 가중치를 가지는 간선을 집합에 포함한다. 이 과정을 반복적으로 N(정점)-1 까지 수행하며 이 과정에서
싸이클이 형성되는 간선 (a,b)는 제외한다.


# Union-find 연산

union-find 연산은 두 간선이 같은 집합에 속해있는지를 확인하기 위해 사용한다.
일반적으로 union-find 연산은 Kruskal의 알고리즘 외에도 널리 사용되고 있다.
union(x,y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합을 합집합으로 만든다.
find(x) 연산은 원소 x가 속해있는 집합(대표 원소)을 반환한다.

Union-find 알고리즘 참조 : http://mgkim.egloos.com/1007300

Kruskal.cpp

#include <stdio.h> 

#define MAX_VERTEX 100
#define MAX_ELEMENT 100

int parent[MAX_VERTEX]; 
int num[MAX_VERTEX]; 

typedefstruct { 
int v; // 정점1
int u; // 정점2
int key; // 간선의 가중치
}Element; 

typedefstruct { 
    Element heap[MAX_ELEMENT]; 
int heap_size; 
}HeapType; 

void InitHeap(HeapType *h) 
{ 
    h->heap_size=0; 
} 
void InsertHeap(HeapType *h,Element item) 
{ 
int i; 
    i=++(h->heap_size); 

while(i != 1 && item.key < h->heap[i/2].key) // 부모노드와 비교
    { 
        h->heap[i]=h->heap[i/2]; 
        i/=2; 
    } 

    h->heap[i]=item; 
} 

Element DeleteHeap(HeapType *h) 
{ 
int parent=1,child=2; 
    Element data,temp; 

    data = h->heap[parent]; 
    temp = h->heap[(h->heap_size)--]; // 삭제에 의한 size 감소

while(child <= h->heap_size) 
    { 
//자식 노드간 작은 수 비교 
if((child < h->heap_size) && (h->heap[child].key) > h->heap[child+1].key)  
            child++; 

if(temp.key <= h->heap[child].key) break; 

        h->heap[parent] = h->heap[child]; 
        parent = child; 
        child *= 2; // 다음 자식 노드와 비교
    } 

    h->heap[parent]=temp; 
return data; 
} 

void InitUF(void) // 전역 변수 초기화
{ 
int i; 
for(i=0;i<MAX_VERTEX;i++) 
    { 
        parent[i]=-1; 
        num[i]=1; 
    } 
} 

int SetFind(int v) // v가 속하는 집합을 반환한다
{ 
int i,p,temp; 

for(i=v;(p=parent[i])>=0;i=p); // 정점v의 루트를 찾는다

    temp=i; // 정점 v를 포함하는 집합의 대표 원소 

for(i=v;(p=parent[i])>=0;i=p)  
        parent[i]=temp; // 집합의 모든 원소들의 부모를 s로 설정

return temp; 
} 

void SetUnion(int v1,int v2) // 두개의 원소가 속한 집합을 합친다
{ 
if(num[v1] < num[v2]) // 자식의 갯수로 비교
    { 
        parent[v1]=v2; // 부모 변경
        num[v1]+=num[v2]; 
    } 
else
    { 
        parent[v2]=v1; // 부모 변경
        num[v2]+=num[v1]; 
    } 
} 

void InsertHeapEdge(HeapType *h,int v,int u,int weight) 
{ 
    Element node; 
    node.v=v; 
    node.u=u; 
    node.key=weight; 

    InsertHeap(h,node); 
} 

int kruskal(int n) 
{ 
    Element e; 
    HeapType h; 
int uSet,vSet,edgeCount=0,sum=0; 

    InitHeap(&h); 
    InitUF(); 

    InsertHeapEdge(&h,0,1,29); 
    InsertHeapEdge(&h,1,2,15); 
    InsertHeapEdge(&h,2,3,12); 
    InsertHeapEdge(&h,3,4,22); 
    InsertHeapEdge(&h,4,5,27); 
    InsertHeapEdge(&h,5,0,10); 
    InsertHeapEdge(&h,6,1,16); 
    InsertHeapEdge(&h,6,3,18); 
    InsertHeapEdge(&h,6,4,25); 

while(edgeCount < n-1) // 간선의 갯수가 n-1이 될 때 까지
    { 
        e=DeleteHeap(&h); // 최소 힙

// 가장 가중치가 가장 낮은 간선을 선택
        uSet=SetFind(e.u);  
        vSet=SetFind(e.v); 

if(uSet != vSet) // 서로의 대표 원소가 같지 않은 경우에만
        { 
            printf("(%d,%d) %d\n",e.u,e.v,e.key); 
            sum+=e.key; 
            edgeCount++; // 간선을 하나 늘린다
            SetUnion(uSet,vSet); // 두 집합을 합친다
        } 
    } 

    printf("최소 비용의 간선 길이 %d \n\n",sum); 

for(int m=0;m<n;m++) 
        printf("자식 [%d] : 부모 %d\n",m,parent[m]); 

return0; 
} 

int main() 
{ 
    kruskal(7); // 현재 간선의 갯수는 7개로 만들어놓았다.
}