kruskal Greedy Method

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100
#define INF 1000

#define MAX_ELEMENT 100
#define TRUE 1
#define FALSE 0
int parent[MAX_VERTICES];
int num[MAX_VERTICES];

typedef struct {
 int key; // 간선의 가중치
 int u;   // 정점1
 int v;   // 정점 2
}element;

void set_init(int n) {
 int i;
 for( i=0; i<n; i++){
  parent[i] = -1;
  num[i] = 1;
 }
}

int set_find(int vertex){
 int p,s, i=-1;
 for( i=vertex; (p=parent[i])>=0; i=p); // i=3, p=1, i=p=1
 s = i;           // i=1, p=0, i=p=0
 for( i=vertex; (p=parent[i])>=0; i=p)  // i=0, p=-1, 종료
  parent[i] = s;        // s=i=0, return s;
 return s;
}

void set_union(int s1, int s2){
 if( num[s1] < num[s2] ){
  parent[s1] = s2;
  num[s2] += num[s1];
 }
 else {
  parent[s2] = s1;
  num[s1] += num[s2];
 }
}

 

typedef struct {
 element heap[MAX_ELEMENT];
 int heap_size;
} HeapType;

// 초기화 함수
void init(HeapType *h)
{
 h->heap_size =0;
}
//
int is_empty(HeapType *h)
{
 if( h->heap_size == 0 )
  return TRUE;
 else
  return FALSE;
}
// 삽입 함수
void insert_min_heap(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 delete_min_heap(HeapType *h)
{
    int parent, child;
    element item, temp;

    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1; 
    child = 2;
    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 item;
}

void insert_heap_edge(HeapType *h, int u, int v, int weight){
 element e;
 e.u = u;
 e.v = v;
 e.key = weight;
 insert_min_heap(h,e);
}

void insert_alledges(HeapType *h){
 insert_heap_edge(h,0,1,29);
 insert_heap_edge(h,1,2,16);
 insert_heap_edge(h,2,3,12);
 insert_heap_edge(h,3,4,22);
 insert_heap_edge(h,4,5,27);
 insert_heap_edge(h,5,0,10);
 insert_heap_edge(h,6,1,15);
 insert_heap_edge(h,6,3,18);
 insert_heap_edge(h,6,4,25);
}

// 인접 행렬이나 인접 리스트에서 간선들을 읽어서 최소 히프에 삽입
// 현재는 예제 그래프의 간선들을 삽입한다.
void insert_all_edges(HeapType *h)
{
 insert_heap_edge(h,0,1,29);
 insert_heap_edge(h,1,2,16);
 insert_heap_edge(h,2,3,12);
 insert_heap_edge(h,3,4,22);
 insert_heap_edge(h,4,5,27);
 insert_heap_edge(h,5,0,10);
 insert_heap_edge(h,6,1,15);
 insert_heap_edge(h,6,3,18);
 insert_heap_edge(h,6,4,25);
}
// (p.431) kruskal의 최소 비용 신장 트리 프로그램
// ...
void kruskal(int n){
 int edge_accepted = 0;
 HeapType h;
 int uset, vset;
 element e;

 init(&h);
 insert_all_edges(&h);
 set_init(n);
 while( edge_accepted <(n-1)){  //간선의수 < (n-1)
  e = delete_min_heap(&h);   // ㄷㄷㄷㄷ
  uset = set_find(e.u);      // 정점 u의 집합
  vset = set_find(e.v);      // 정점 v의 집합
  if( uset != vset){         // 서로 속한 집합이 다르면
   printf("(%d,%d) %d \n", e.u, e.v, e.key);
   edge_accepted++;
   set_union(uset, vset);  // 두개의 집합을 합친다.
  }

 }

}

int main(void)
{
 kruskal(7);  // 인수: 정점의 개수
 
 
 return 0;
}