克鲁斯卡尔算法的C实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX 100
 
/* 定义边(x,y)，权为w */
typedef struct
{
	int x, y;
	int w;
}edge;
 
edge e[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
int sum;
 typedef int (*cmptr)(const int a, const int b);
/* 比较函数，按权值(相同则按x坐标)非降序排序 */
int cmp(const int a, const int b)
{
	if (a == b)
	{
		return (a - b);
	}
	return (a-b);
}
/*堆排序*/
void HeapAdjust(edge *e,int s,int m)
{
	edge *rc=(edge*)malloc(sizeof(edge));
		*rc=e[s];
    for(int j=2*s;j<=m;j*=2)
	{
		if(j<m && cmp(e[j].w,e[j+1].w)<0) j++;
		if(cmp(rc->w,e[j].w)>0) break;
		e[s]=e[j];
		s=j;
	
	}
	e[s]=*rc;
}
void qsort(edge *e, int n, cmptr fun)
{
	//建大顶堆
	for(int i=n/2;i>0;i--)
	{
		HeapAdjust(e,i,n);
	}
	//排序
	edge *temp=(edge*)malloc(sizeof(edge));
	for(i=n;i>0;i--)
	{
	  *temp=e[1];
	  e[1]=e[i];
	  e[i]=*temp;

	  //e[i].w=0;
      HeapAdjust(e,1,i-1);

	}
  
}

/* 初始化集合 */
void Make_Set(int x)
{
	father[x] = x;
	rank[x] = 0;
}
 
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
	if (x != father[x])
	{
		father[x] = Find_Set(father[x]);
	}
	return father[x];
}
 
/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{
 
	if (x == y) return;
	/* 将秩较小的树连接到秩较大的树后 */
	if (rank[x] > rank[y])
	{
		father[y] = x;
	}
	else
	{
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
		father[x] = y;
	}
	sum += w;
}
 
/* 主函数 */
int main()
{
	int i, n;
	int x, y;
	char chx, chy;
 
	/* 读取边的数目 */
	scanf("%d", &n);
	getchar();
 
	/* 读取边信息并初始化集合 */
	for (i = 1; i <=n; i++)
	{
		scanf("%c %c %d", &chx, &chy, &e[i].w);
		getchar();
		e[i].x = chx - 'A'+1;
		e[i].y = chy - 'A'+1;

		Make_Set(i);
	}
 
	/* 将边排序 */
	qsort(e, n, cmp);
 
	sum = 0;
 
	for (i = 1; i <=n; i++)
	{
		x = Find_Set(e[i].x);
		y = Find_Set(e[i].y);
		if (x != y)
		{
			printf("%c - %c : %d\n",e[i].x + 'A'-1, e[i].y + 'A'-1, e[i].w);
			Union(x, y, e[i].w);
		}
	}
 
	printf("Total:%d\n", sum);
	//system("pause");
	return 0;	
}