kruscal.cpp

kruscal算法构造最小生成树

#include <stdio.h>
#include <algorithm>
using namespace std;
#define SIZE 1001

/*存储策略***************************************
father[SIZE]存放n个结点的父指针
rank[SIZE]存放各结点在生成树中的高度,以便在合并时让低的指向高的,是合并树不会太高
l[SIZE*SIZE]存放各边的信息
*/
int m,n,father[SIZE],rank[SIZE];

struct bian//边的数据结构
{
       int x,y,n;//x:form,y:to,n:distance
}l[SIZE*SIZE]={//初始化边表,若用test1()测试,则使用此表;
	{0,0,0},   //若用test2(),则以输入的新内容覆盖
	{1,2,34},
	{1,6,19},
	{1,3,46},
	{3,6,25},
	{3,4,17},
	{4,6,25},
	{4,5,38},
	{5,6,26},
	{5,2,12},
	};

//比较函数
bool cmp(struct bian x,struct bian y)
{
       return (x.n<y.n);
}

//以结点查找父母结点的函数find()
int find(int i)
{
       if (father[i]==i)       return i;
       father[i]=find(father[i]);
       return father[i];
}

//合并两边的函数combine(x,y)即union,让结点y指向x
void combine(int x,int y)
{
       father[y]=x;//让结点y指向x
       if (rank[x]==rank[y])       rank[x]++;//未更新前若x和y同高,则合并后x应比y
}                                            //高一级,所以x+1;否则,

//比较将要合并的两树的高度(即两根的高度),并让低的指向高的
void tackle(int x,int y)
{
       if (rank[x]>rank[y])  combine(x,y);//x比y高
       else                  combine(y,x);//x<=y时,在combine(x,y)中另行判断相等情况
}

//构造最小生成树的kruskal()方法***********************************
void kruskal()
{
       int i,t;
       sort(l+1,l+m+1,cmp);//边排序
       for (t=i=1;t<n;i++)//t为并入点数
             if (find(l[i].x)!=find(l[i].y))//是否在一个集合
             {
                 printf("%d次\t%d<-->%d\t权值为：%d\n",t,l[i].x,l[i].y,l[i].n);//输出此边
                 t++;
                 tackle(father[l[i].x],father[l[i].y]);//更新,即合并
             }
}

//测试方法一，不需用户输入，测试已有图形
void test1()
{
	int i,t;	
	m=9;
	n=6;
    for(t=1;t<=m;t++)
		printf("%d\t%d\t%d\n",l[t].x,l[t].y,l[t].n);
    for (i=1;i<=n;i++) father[i]=i;//并查集初始化
    memset(rank,0,sizeof(rank));
    kruskal();
}

//测试方法二，要求用户输入，有些麻烦，不过灵活些
void test2()
{
	   int i;
	   printf("请输入边数和点数：");
       scanf("%d%d",&m,&n);//m边n点
       for (i=1;i<=m;i++)//边数
             scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].n);//若有重边还需另加判断
       for (i=1;i<=n;i++)       father[i]=i;//并查集初始化
       memset(rank,0,sizeof(rank));
       kruskal();
}

//主函数
main()
{
	test1();
	return 0;
}