main.cpp

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

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

int distance(int x1,int y1,int x2,int y2)
{
	return int(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}

void main()
{
	int total=0;
	clock_t t1,t2;
	int i,j,k;
	srand(time(0));
	point P[n+1];
	//生成二维数组B[n+1][n+1]
	typedef int* Row; 
	t1=clock();
	int row=n+1, col=n+1; 
	Row* B= new Row[row]; 
	for(i = 0; i < row; ++i) 
	{ 
		B[i] = new int[col]; 
	}
	//生成array A[(n+1)*(n+1)+1]
	array *A;
	A=new array [(n+1)*(n+1)+1];
	t2=clock();
	cout<<"t1="<<t2-t1<<endl;
	t1=clock();
	for(i=1;i<=n;i++)
	{
		P[i].x=rand();
		P[i].y=rand();
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)
			{
				B[i][j]=0;
			}
			else
			{
				B[i][j]=-1;
			}
		}
	}
	t2=clock();
	cout<<"t2="<<t2-t1<<endl;
	k=0;
	int r;
	t1=clock();
	for(i=1;i<n;i++)
	{
		r=rand()%(n-i);
		
		for(j=i+1;j<=i+1+r&&j<=n;j++)
		{
			total=total+1;
			B[i][j]=distance(P[i].x,P[i].y,P[j].x,P[j].y);
			k++;
			A[k].data=B[i][j];
			A[k].num=(i-1)*n+j;
		}
	}
	t2=clock();
	cout<<"t3="<<t2-t1<<endl;
/*	//输出邻接矩阵
	cout<<"生成图的邻接矩阵为"<<'\n';
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(B[i][j]<0)
			{
				cout<<"∞"<<'\t';
			}
			else
			{
				cout<<B[i][j]<<'\t';
			}
		}
		cout<<endl;
	}
*/
	cout<<total<<endl;
	t1=clock();
	kruskal(A,k);
	t2=clock();
	cout<<"t4="<<t2-t1<<endl;
	for(i = 0; i < row; ++i) 
	{ 
		delete [] B[i]; 
	} 
	delete [] B;
}