main.cpp

本程序是用来prim算法用C++的完全实现,可供大家学习使用.

#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()
{
	clock_t t1,t2;
	srand(time(0));
	point P[n+1];
	int i,j;
	AdjList G;
//	int r;
	ArcNode *s,*p;
	for(i=1;i<=n;i++)
	{
		P[i].x=rand();
		P[i].y=rand();
	}
	for(i=1;i<=n;i++)
	{
		G[i].num=i;
		G[i].firstarc=NULL;
		G[i].tailarc=NULL;
	}
	for(i=1;i<n;i++)
	{
//		r=rand()%(n-i);
		for(j=i+1;j<=i+1&&j<=n;j++)
		{
			//结点j插入结点i的邻接表中
			s=new ArcNode;
			s->num=j;
			s->data=distance(P[i].x,P[i].y,P[j].x,P[j].y);
			if(G[i].firstarc==NULL)
			{
				G[i].firstarc=s;
			}
			else
			{
				G[i].tailarc->nextarc=s;
			}
			G[i].tailarc=s;
			//结点i插入结点j的邻接表中
			p=new ArcNode;
			p->num=i;
			p->data=s->data;
			if(G[j].firstarc==NULL)
			{
				G[j].firstarc=p;
			}
			else
			{
				G[j].tailarc->nextarc=p;
			}
			G[j].tailarc=p;
			G[j].tailarc->nextarc=NULL;
		}
		G[i].tailarc->nextarc=NULL;
	}
	//输出图的邻接表
/*	cout<<"生成随机图的邻接表为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		p=G[i].firstarc;
		cout<<i<<"->";
		while(p!=NULL)
		{
			cout<<p->num<<"["<<p->data<<"]"<<"->";
			p=p->nextarc;
		}
		cout<<"NULL"<<endl;
	}
*/

	t1=clock();
	prim(G);
	t2=clock();
	cout<<"t="<<t2-t1<<endl;
	for(i=1;i<=n;i++)
	{
		while(G[i].firstarc!=NULL)
		{
			p=G[i].firstarc;
			G[i].firstarc=p->nextarc;
			delete p;
		}
	}
}