prim.cpp

算法分析与设计

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

struct vertex
{
	int x,y;
};

struct ArcNode  //定义边表结点
{
	int av;   //邻接点域
	int w;
	ArcNode* next;
};

struct VexNode  //定义头结点
{
	vertex vex;
	ArcNode* first;
	bool flag;
};

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

void Graph(VexNode adj[],int n,int e,int &a)
{
	int c=999999;
	for(int i=0;i<n;i++)
	{
		adj[i].vex.x=rand();
		adj[i].vex.y=rand();
		adj[i].first=NULL;
		adj[i].flag=0;
	}
	for(int j=1;j<n;j++)
	{
		int r=rand()%j;
		ArcNode* s=new ArcNode;
		s->av=j;
		s->next=adj[r].first;
		adj[r].first=s;
		s->w=(int)sqrt(pow(adj[r].vex.x-adj[j].vex.x,2)+pow(adj[r].vex.y-adj[j].vex.y,2));
		
		ArcNode* t=new ArcNode;
		t->av=r;
		t->next=adj[j].first;
		adj[j].first=t;
		t->w=s->w;

		if(s->w<c)
		{
			c=s->w;
			a=s->av;
		}
	}
	int f=e-n+1;
	while(f>0)
	{
		ran:
		int r1=rand()%n;
		int r2=rand()%n;
		while(r1==r2)
		{
			r2=rand()%n;
		}
		ArcNode *p=adj[r1].first;
		while(p!=NULL)
		{
			if(p->av!=r2)  p=p->next;
			else  goto ran;
		}
		if(p==NULL)
		{
			ArcNode* s=new ArcNode;
			s->av=r2;
			s->next=adj[r1].first;
			adj[r1].first=s;
		    s->w=(int)sqrt(pow(adj[r1].vex.x-adj[r2].vex.x,2)+pow(adj[r1].vex.y-adj[r2].vex.y,2));

			ArcNode* t=new ArcNode;
			t->av=r1;
			t->next=adj[r2].first;
			adj[r2].first=t;
			t->w=s->w;

			if(s->w<c)
			{
				c=s->w;
				a=s->av;
			}
		}
		f--;
	}
}

void SIFT_DOWN(edge x[],int k,int m)
{
	edge temp;
	int i=k, j=2*(i+1)-1;                 //置i为要筛的结点，j为i的左孩子
	while(j<=m)                           //筛选还没进行到叶子结点
	{
		if(j<m && x[j].cost>x[j+1].cost) j++;       //比较i的左右孩子，j为较大者
		if(x[i].cost<=x[j].cost) 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+1)-1;                           //被筛结点位于原来结点j的位置
		}
	}
}

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

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

int compare(const void *a,const void *b)
{
	return ((edge *)a)->beg - ((edge *)b)->beg;
}

int BinSearch(edge x[],int low,int high,int k)
{
	if(low>high) return 0;
	else
	{
		int mid=(low+high)/2;
		if(k<x[mid].beg) return BinSearch(x,low,mid-1,k);
		else if(k>x[mid].beg)  return BinSearch(x,mid+1,high,k);
		else return mid;
	}
}

void prim(VexNode adj[],edge T[],edge C[],int n,int a)
{
	edge min;
	int *N=new int[n];
	for(int i=0;i<n;i++)
	{	
		C[i].cost=999999;
		ArcNode *t=adj[i].first;
		while(t!=NULL)
		{
			C[t->av].beg=t->av;
			t=t->next;
		}
	}
    ArcNode *p=adj[a].first;
	while(p!=NULL)
	{
	    N[p->av]=a;
		C[p->av].cost=p->w;
		C[p->av].beg=p->av;
		p=p->next;
	}
	adj[a].flag=1;
	//cout<<a<<endl;
	for(int j=1;j<n;j++)
	{
		//int h=n-1;
		Heap(C,n-1);
		Del:
		min=DeleteMin(C,n-1);
		//cout<<min.beg<<" "<<min.cost<<endl;
		if(adj[min.beg].flag==0)
		{	
			adj[min.beg].flag=1;
			T[j].beg=N[min.beg];
			T[j].end=min.beg;
			T[j].cost=min.cost;
		}
		else goto Del;
		qsort((void*)C,n,sizeof(edge),compare);
		ArcNode *q=adj[min.beg].first;
		while(q!=NULL)
		{
			if(adj[q->av].flag==0)
			{
				int key=q->av;
				int z;
				z=BinSearch(C,0,n-1,key);
				if(q->w<=C[z].cost)
				{
					N[q->av]=min.beg;
					C[z].cost=q->w;
					C[z].beg=q->av;
				}
			}
			q=q->next;
		}
	}
}

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