kruskal.cpp

算法设计与分析kruskal算法实现

#include <iostream.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

struct vertex
{
	int x,y;
};

struct edge
{
	int beg,end;
	int w;
};

void Graph(vertex vex[],edge arc[],int n,int e)
{
	int f=e;
	for(int i=0;i<n;i++)
	{
		vex[i].x=rand();  vex[i].y=rand();
		//cout<<vex[i].x<<","<<vex[i].y<<endl;
	}
	for(int j=1;j<n;j++)
	{
		int r=rand()%j;
		arc[e].beg=r;   arc[e].end=j;
		arc[e].w=(int)(sqrt(pow(vex[r].x-vex[j].x,2)+pow(vex[r].y-vex[j].y,2)));
		//cout<<arc[e].w<<endl;
		e--;
	}
    out:
	while(e>0)
	{
		int r1=rand()%n;
		int r2=rand()%n;
		while(r1==r2)
		{
			r2=rand()%n;
		}
		for(int k=f;k>0;k--)
		{
			if(arc[k].beg==r1 && arc[k].end!=r2)
			{
				arc[e].beg=r1;   arc[e].end=r2;
				arc[e].w=(int)(sqrt(pow(vex[r1].x-vex[r2].x,2)+pow(vex[r1].y-vex[r2].y,2)));
				//cout<<arc[e].w<<endl;
				e--;
				goto out;
			}
		}
	}
}

void SIFT_DOWN(edge x[],int k,int m)
{
	edge temp;
	int i=k, j=2*i;                 //置i为要筛的结点，j为i的左孩子
	while(j<=m)                           //筛选还没进行到叶子结点
	{
		if(j<m && x[j].w>x[j+1].w) j++;       //比较i的左右孩子，j为较大者
		if(x[i].w<=x[j].w) break;              //根结点已经大于左右孩子中的较大者
		else
		{
			temp=x[i];  x[i]=x[j];  x[j]=temp;
			/*temp.beg = x[i].beg;  temp.end = x[i].end;  temp.w = x[i].w;
			x[i].beg = x[j].beg;  x[i].end = x[j].end;  x[i].w = x[j].w; 
			x[j].beg = temp.beg;  x[j].end = temp.end;  x[j].w = temp.w; */     //将根结点与子结点j交换
			i = j; j = 2*i;                           //被筛结点位于原来结点j的位置
		}
	}
}

void Heap(edge x[],int n)                 //堆排序
{
	for(int i = n/2; i>0; i--)       //创建堆，从最后一个非终结点至根结点
		SIFT_DOWN(x,i,n);
}

edge DeleteMin(edge x[],int e)
{
	edge z=x[1];
	edge y=x[e];
	e=e-1;
	x[1]=y;
	SIFT_DOWN(x,1,e);
	return z;
}

void kruskal(edge arc[],edge T[],int n,int e)
{
	Heap(arc,e);
	int *flag=new int[n];
	int q=1;
	for(int d=0;d<n;d++)
	{
		flag[d]=0;	
	}
	for(int m=1;m<=e;m++)
	{
		edge ee=DeleteMin(arc,e);
		//cout<<ee.w<<endl;
		if(flag[ee.beg]!=0 && flag[ee.end]!=0 && flag[ee.beg]==flag[ee.end]) 
		{
			T[m].beg=ee.beg;   T[m].end=ee.end;   T[m].w=0;
		}
		else if(flag[ee.beg]==0 && flag[ee.end]==0)
		{	
			T[m].beg=ee.beg;   T[m].end=ee.end;   T[m].w=ee.w;
			flag[ee.beg]=q;    flag[ee.end]=q;
			q++;
		}
		else if(flag[ee.beg]!=0 && flag[ee.end]!=0 && flag[ee.beg]!=flag[ee.end])
		{
			T[m].beg=ee.beg;   T[m].end=ee.end;	  T[m].w=ee.w;
			for(int i=1;i<=e;i++)
			{
				if(flag[arc[i].beg]==flag[ee.beg] || flag[arc[i].beg]==flag[ee.end])  flag[arc[i].beg]=q;
				if(flag[arc[i].end]==flag[ee.beg] || flag[arc[i].end]==flag[ee.end])  flag[arc[i].end]=q;
			}
			q++;
		}
		else
		{
			T[m].beg=ee.beg;   T[m].end=ee.end;   T[m].w=ee.w;
			if(flag[ee.beg]==0)  flag[ee.beg]=q;
			else
			{
				for(int i=1;i<=e;i++)
				{
					if(flag[arc[i].beg]==flag[ee.beg]) flag[arc[i].beg]=q;
					if(flag[arc[i].end]==flag[ee.beg]) flag[arc[i].end]=q;
				}
			}
			if(flag[ee.end]==0)  flag[ee.end]=q;
			else
			{
				for(int i=1;i<=e;i++)
				{
					if(flag[arc[i].end]==flag[ee.end])  flag[arc[i].end]=q;
					if(flag[arc[i].beg]==flag[ee.end])  flag[arc[i].beg]=q;
				}
			}
			q++;
		}
	}
}

void main()
{
	clock_t t1,t2;
	double t,sum = 0.0,avg;
	int a,b;
	cout<<"请输入图中顶点的个数：";
	cin>>a;
	cout<<"\n请输入图中边的条数：";
	cin>>b;
	vertex *V=new vertex[a];
	edge *E=new edge[b+1];
	edge *T=new edge[b+1];
	for(int j = 0; j<10; j++)
	{
		Graph(V,E,a,b);	
		t1 = clock();
		kruskal(E,T,a,b);
		t2 = clock();                     
		t = (double)(t2 - t1)/CLOCKS_PER_SEC;
		sum=+t;
		/*for(int i=1;i<=b;i++)
		{
			cout<<T[i].end<<","<<T[i].beg<<endl;
			cout<<T[i].w<<"\n\n";
		}
		cout<<"**************\n";*/
	}
	avg = sum/10.0;
	cout<<"\n\n测试10次，平均耗时为"<<avg<<"s\n\n";
}