#include <stdio.h>
#include <stdlib.h>
typedef struct edge{ //edge 형 변수
int left; //int형변수 left,right,weight,u를 포함한다.
int right;
int weight;
int u; // 어떤 집합에 속할지 정해준다.
}edge;
void Kruskal(edge E[],edge T[]);
void select_sort(edge vector[],int size);
int notcycle(edge *e,edge T[]);
int makeuni(edge *e,edge T[]);
void jointuni(edge T[]);
int uni=0; //전역변수, 집합의 이름(번호)를 정함
int Ecount=0; //E의 인덱스
int Tlength=0; //T의 길이(T에 원소 몇개인지)
edge T[6]; //edge형 배열 T 크기 6
edge E[9]; //edge형 배열 E 크기 9
int k;
int main(void)
{
int i;
for(i=0;i<20;i++){
T[i].left=-1; T[i].right=-1; T[i].u=-1; T[i].weight=-1;} //T 초기화 (안나올 값으로)
E[0].left=5; E[0].right=0; E[0].weight=10; E[0].u=-1;
E[1].left=0; E[1].right=1; E[1].weight=28; E[1].u=-1;
E[2].left=1; E[2].right=2; E[2].weight=16; E[2].u=-1;
E[3].left=2; E[3].right=3; E[3].weight=12; E[3].u=-1;
E[4].left=6; E[4].right=3; E[4].weight=18; E[4].u=-1;
E[5].left=4; E[5].right=3; E[5].weight=22; E[5].u=-1;
E[6].left=4; E[6].right=6; E[6].weight=24; E[6].u=-1;
E[7].left=5; E[7].right=4; E[7].weight=25; E[7].u=-1;
E[8].left=6; E[8].right=1; E[8].weight=14; E[8].u=-1; //교과서에 나온 것처럼 초기화
Kruskal(E,T); //Kruscal 알고리즘 실행
for(i=0;i<6;i++)
{printf("%d %d %d %d\n",T[i].left,T[i].right,T[i].u,T[i].weight);} //출력으로 제대로 나왔나 확인
return 0;
}
void Kruskal(edge E[],edge T[]){
edge temp;
select_sort(E,9); //E를 가중치의 크기대로 오름차순 정렬한다.
while((Tlength<6)&&(Ecount<9)){ //Tlength가 6보다 작고 Ecount가 9보다 작으면 루프 반복
temp.left=E[Ecount].left;temp.right=E[Ecount].right;temp.weight=E[Ecount].weight; temp.u=E[Ecount].u; //temp의 각 요소에 E[Ecount]의 요소 대입
E[Ecount].left=-1;E[Ecount].right=-1;E[Ecount].weight=-1; //E의 Ecount 원소는 삭제 (-1대입)
makeuni(&temp,T); //temp의 집합을 만들어준다.
jointuni(T); //같은 집합인데 번호가 다른 집합이 있으면 합해준다. temp를 제외한 T만 해준다. (cycle 검사때문에)
for(k=0;k<Tlength;k++){
printf("T[%d].u=%d ",k,T[k].u);
}
printf("tmp.u : %d\n",temp.u); //T의 원소의 집합 번호와 temp의 집합 번호 확인
if(notcycle(&temp,T)) //싸이클이 생기지 않으면
{
T[Tlength].left=temp.left;T[Tlength].right=temp.right;T[Tlength].weight=temp.weight; T[Tlength].u=temp.u; //T[Tlength]의 요소에 temp의 요소 대입
Tlength++;Ecount++; //Tlength와 Ecount 하나씩 증가
}
else{Ecount++;} //싸이클이 생겼으면 Ecount만 증가
}}
void select_sort(edge vector[],int size){ //선택정렬 알고리즘
int i; int j; int temp; int index;
for(i=0;i<size;i++)
{
index=i;
for(j=i+1;j<size;j++)
{
if((vector[j].weight)<vector[index].weight){
index=j;}
}
temp=vector[index].weight;
vector[index].weight=vector[i].weight;
vector[i].weight=temp;
temp=vector[index].left;
vector[index].left=vector[i].left;
vector[i].left=temp;
temp=vector[index].right;
vector[index].right=vector[i].right;
vector[i].right=temp;
}
}
int notcycle(edge *e,edge T[]){ //간선이 cycle 형성 하는지 리턴값이 판별 1이면 notcycle, 0이면 cycle
int check=0;
int i;
if(Tlength==0) //Tlength가 0이면 1반환
return 1;
for(i=0;i<Tlength;i++){ //i=0부터 Tlength 이전까지 반복
if(e->u==T[i].u){ //e->u 와 T[i].u 가같으면 (집합이 같으면)
if((e->left==T[i].left)||(e->left==T[i].right)||(e->right==T[i].left)||(e->right==T[i].right)){ //e의 left가 t의 left나 right와 같거나, e의 right가 t의 left나 right와 같거나
check++;
printf("Tlength=%d i=%d check=%d\n\n",Tlength,i,check);} //check 증가식
if(check==2) //즉 같은 집합 내에서
{return 0;}
}}
return 1;
}
int makeuni(edge *e,edge T[]){ //집합을 만드는 함수
int i; int check=0;
if(Tlength==0) //Tlength가 0이면
{e->u=uni++; return e->u;} //e->u에 uni 대입하고 증가, e->u 리턴
else{
for(i=0;i<Tlength;i++)
{
if((e->left==T[i].left)||(e->left==T[i].right)||(e->right==T[i].left)||(e->right==T[i].right)) //e의 left가 t의 left나 right와 같거나, e의 right가 t의 left나 right와 같거나
{check=1; //check에 1 대입
e->u=T[i].u; return e->u; //e->u 에 T[i].u 대입 (즉 둘은 같은 집합이됨) e->u 리턴
break;}
}
if(check==0){ //check가 0이면
e->u=uni++; return e->u; //e->u에 uni대입하고 uni 증가시킴, e->u 리턴 (새로운집합)
}}}
void jointuni(edge T[]){ //집합을 합치는 함수
int i;
for(i=0;i<Tlength;i++){ //i=0부터 Tlength 보다 작을때까지 반복
if((T[i+1].left==T[i].left)||(T[i+1].left==T[i].right)||(T[i+1].right==T[i].left)||(T[i+1].right==T[i].right)){ //T[i+1]의 left가 T[i]의 left나 right와 같거나, T[i+1]의 right가 T[i]의 left나 right와 같거나,
if(T[i+1].u<T[i].u) //T[i+1].u가 T[i].u보다 작으면
T[i].u=T[i+1].u; //T[i+1].u를 T[i].u에 대입
else
T[i+1].u=T[i].u; //작은 쪽으로 집합 번호를 매긴다.
}}}
