kruskal.cpp

本算法是一个关于kruskal的源码实现,可供大家学习研究.

#include <iostream.h>
#include <time.h>
#include "head.h"

int FIND(int i,int V[])
{
	int y=i;
	while(V[y]!=y)
	{
		y=V[y];
	}
	int w,root=y;y=i;
	while(V[y]!=y)
	{
		w=V[y];
		V[y]=root;
		y=w;
	}
	return root;
}
void UNION(int i,int j,int V[])
{
	int u=FIND(i,V),v=FIND(j,V);
	V[u]=j;
}


void kruskal(array A[],int k)
{
	int i,j;
	int V[n+1];             //顶点集合
	int T[n];               //生成树的序号存储
	int t_num=1;            //生成树序号
	int e=1;                //边的序号
	heapsort(A,k);          //按非降序权重将E中的边排序
	for(i=1;i<=n;i++)		//对每个顶点,构建一个集合
	{
		V[i]=i;
	}
	while(t_num<n)
	{
		i=(A[e].num-1)/n+1;
		j=A[e].num-(i-1)*n;
		if(FIND(i,V)!=FIND(j,V))
		{
			T[t_num++]=A[e].num;
			UNION(i,j,V);
		}
		e++;
	}
	//输出生成树T中的边(i,j)
/*	cout<<"生成树的边对为:"<<'\n';
	for(t_num=1;t_num<n;t_num++)
	{
		i=(T[t_num]-1)/n+1;
		j=T[t_num]-(i-1)*n;
		cout<<"("<<i<<","<<j<<")"<<'\t';
	}
	cout<<endl;
*/
 }