크루스칼 알고리즘(Kruskal's algorithm)

소개글

크루스칼 알고리즘(Kruskal's algorithm)에 대한 보고서 자료입니다.

목차

개 념
진 행 절 차
<소스 코드>
<결과 화면>

본문내용

; k++)/*손자노드를 가지고 있는 노드가 */
if(u[k].parent == temp) /*합병되어 부모가 바뀐경우 손자의 부모도*/
u[k].parent = c;/*바꿔 준다*/
}
int notequal(int p, int q)/*p와 q가 다른지를 비교*/
{
if(p == q)
return 0;
else
return 1;
}
void initial(int n)/*정점의 집합을 초기화*/
{
int i;
for(i = 1; i <= n; i++)
makeset(i);
}
void quicksort(int low, int high)/*가중치의 집합을 비내림차순으로 정렬*/
{/*퀵소트*/
if(high > low){
Pivotpoint = partition(low, high, Pivotpoint);
quicksort(low, Pivotpoint - 1);
quicksort(Pivotpoint + 1, high);
}
}
int partition(int low, int high, int Pivotpoint) /*퀵소트의 나누는 함수*/
{
int i, j;
int pivotitem;
edge temp;
pivotitem = E[low].weight;
j = low;
for(i = low + 1; i <= high; i++){
if(E[i].weight < pivotitem){
j++;
temp = E[i];
E[i] = E[j];
E[j] = temp;
}
}
Pivotpoint = j;
temp = E[low];
E[low] = E[Pivotpoint];
E[Pivotpoint] = E[low];
return Pivotpoint;
}
void kruskal(int n, int m)/*크루스칼 알고리즘의 본체*/
{
int c = 1;
int c2 = 1;
int i,j;
int p,q;
edge e;
quicksort(1, n);/*가중치 집합 정렬*/
for(i=1; i <= n-1; i++)/*F[] 초기화*/
{
F[i].pair1 = 0;
F[i].pair2 = 0;
F[i].weight = 0;
}
initial(n);/*정점의 집합 초기화*/
while(c <= m){/*가중치를 선택하여 F[]에 저장*/
e = E[c];/*가중치가 작은것 부터 선택*/
i = e.pair1;/*연결된 정점의 인텍스*/
j = e.pair2;
p = find(i);/*각 정점의 부모 노드 확인*/
q = find(j);
if(notequal(p,q)){/*부모 노드가 다르면 합침*/
merge(p,q);
F[c2] = e;/*F[]에 선택된 가중치를 추가*/
c2++;
}
c++;
}
}
void main()
{
int i;
E[1].pair1 = 2;/*정점간 가중치의 초기화*/
E[1].pair2 = 4;
E[1].weight = 6;
E[2].pair1 = 1;
E[2].pair2 = 2;
E[2].weight = 1;
E[3].pair1 = 1;
E[3].pair2 = 3;
E[3].weight = 3;
E[4].pair1 = 4;
E[4].pair2 = 5;
E[4].weight = 5;
E[5].pair1 = 2;
E[5].pair2 = 3;
E[5].weight = 3;
E[6].pair1 = 3;
E[6].pair2 = 4;
E[6].weight = 4;
E[7].pair1 = 3;
E[7].pair2 = 5;
E[7].weight = 2;
kruskal(5, 7);
for(i = 1; i <= 4; i++)/*선택된 가중치의 집합을 출력=최소신장 트리*/
printf(\"%d -> %d\\n\",F[i].pair1, F[i].pair2);
}

키워드

Kruskal,   크루스칼,   알고리즘