prim.cpp

实现了PRIM算法

#include<time.h>
#include<stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <utility>
#include <math.h>
#include "windows.h"
#include "tchar.h"

#define NUM 500
#define INFINITY -1
#define UNVISITED -254
#define VISITED 254
using namespace std;

double getTime2()//使用高精度计时器
{     
	static LARGE_INTEGER s_freq;
	LARGE_INTEGER performanceCount;
	double t;
	if (s_freq.QuadPart==0)
	{
		if ( !QueryPerformanceFrequency( &s_freq))
			return 0;
	}
	
	QueryPerformanceCounter( &performanceCount );
	t=(double)performanceCount.QuadPart / (double)s_freq.QuadPart;
	return t;
}

typedef pair<int,int> point;

class DijkElem{
public:
	int vertex,distance;
	DijkElem(){vertex=-1;distance=-1;}
	DijkElem(int v,int d){vertex-v,distance=d;}
};

class Graph
{
private:
	int numvertex;
	int numedge;
	int **matrix;
	int *mark;
	point *points;
public:
	Graph(int numvert)
	{
		int i,j;
		numvertex=numvert;
		numedge=0;
		points=new point[numvert];
		mark=new int[numvert];
		for(i=0;i<numvertex;i++)
			mark[i]=UNVISITED;
		matrix=(int**)new int*[numvertex];
		for(i=0;i<numvertex;i++)
			matrix[i]=new int[numvertex];
		for(i=0;i<numvertex;i++)
			for(j=0;j<numvertex;j++)
				matrix[i][j]=INFINITY;
	}
	~Graph()
	{
		delete []mark;
		for(int i=0;i<numvertex;i++)
			delete []matrix[i];
		delete[] matrix;
	}
	int n()
	{
		return numvertex;
	}
	int e()const
	{
		return numedge;
	}
	int first(int v)
	{
		int i;
		for(i=0;i<numvertex;i++)
			if(matrix[v][i]!=INFINITY||matrix[i][v]!=INFINITY)
				return i;
		return i;
	}

	int next(int v1,int v2)
	{
		int i;
		for(i=v2+1;i<numvertex;i++)
			if(matrix[v1][i]!=INFINITY||matrix[i][v1]!=INFINITY)
				return i;
		return i;
	}

	void setpoint(int pos,int x,int y)
	{
		if(pos>=numvertex||pos<0)
			return;
		this->points[pos].first=x;
		this->points[pos].second=y;
	}

	void setedge(int v1,int v2)///////////////////////
	{
		if(matrix[v1][v2]==INFINITY)
			numedge++;
		matrix[v1][v2]=sqrt(pow(this->points[v1].first-this->points[v2].first,2)+
			pow(this->points[v1].second-this->points[v2].second,2));
		matrix[v2][v1]=sqrt(pow(this->points[v1].first-this->points[v2].first,2)+
			pow(this->points[v1].second-this->points[v2].second,2));
	}

	void setedge(int v1,int v2,int wgt)
	{
		if(wgt<0)
		{
			cout<<"Illegal weight value"<<endl;
			return;
		}
		if(matrix[v1][v2]==INFINITY)
			numedge++;
		matrix[v1][v2]=wgt;
		matrix[v2][v1]=wgt;
	}

	int weight(int v1,int v2)
	{
		return matrix[v1][v2];
	}
	int getMark(int v)
	{
		return mark[v];
	}
	void setMark(int v,int val)
	{
		mark[v]=val;
	}
};

template <class Elem,class Comp> class minheap{
private:
	Elem*Heap;
	int size;
	int n;
	void siftdown(int);
public:
	minheap(Elem *h,int num,int min)
	{
		Heap=h; n=num; size=min; buildHeap();
	}
	bool isLeaf(int pos)const
	{
		return (pos>=n/2)&&(pos<n);
	}
	int leftchild(int pos) const
	{
		return 2*pos+1;
	}
	int rightchild(int pos) const
	{
		return 2*pos+2;
	}
	int parent(int pos) const
	{
		return (pos-1)/2;
	}
	bool removemin(Elem&);
	bool insert(const Elem&);
	void buildHeap()
	{
		for(int i=n/2-1;i>=0;i--)
			siftdown(i);
	}
};

template<class Elem,class Comp>
void minheap<Elem,Comp>::siftdown(int pos)
{
	while(!isLeaf(pos)){
		int j=leftchild(pos);
		int rc=rightchild(pos);
		if((rc<n)&&Comp::gt(Heap[j],Heap[rc]))
			j=rc;
		if(!Comp::gt(Heap[pos],Heap[j])) return;
		swap(Heap,pos,j);
		pos=j;
	}
}

template<class Elem,class Comp>
bool minheap<Elem,Comp>::removemin(Elem &it)
{
	if(n==0) return false;
	swap(Heap,0,--n);
	if(n!=0) siftdown(0);
	it=Heap[n];
	return true;
}

template<class Elem,class Comp>
bool minheap<Elem,Comp>::insert(const Elem& val)
{
	if(n>=size) return false;
	int curr=n++;
	Heap[curr]=val;
	while((curr!=0)&&(Comp::lt(Heap[curr],Heap[parent(curr)])))
	{
		swap(Heap,curr,parent(curr));
		curr=parent(curr);
	}
	return true;
}

class DDComp
{
public:
	static bool lt(DijkElem i,DijkElem j)
	{
		return i.distance<j.distance;
	}
	static bool eq(DijkElem i,DijkElem j)
	{
		return i.distance==j.distance;
	}
	static bool gt(DijkElem i,DijkElem j)
	{
		return i.distance>j.distance;
	}
};

template <class Elem> void swap(Elem A[],int i,int j)
{
	Elem temp=A[i];
	A[i]=A[j];
	A[j]=temp;
}

void initD(int *D,Graph *G,int s,int n)
{
	for(int i=0;i<n;i++)
	{
		if(s!=i)
			D[i]=G->weight(s,i);
		else 
			D[i]=0;
		
	}
	
}

void AddEdgetoMST(Graph *G,int V,int v)
{
	for(int w=G->first(v);w<G->n();w=G->next(v,w))
	{
		if(G->getMark(w)==VISITED&&G->weight(w,v)>G->weight(V,v))
			V=w;
	}
}

void Prim(Graph *G, int * D,int *V,int s)
{
	int i,v,w;
	DijkElem temp;
	DijkElem *E=new DijkElem[G->e()];
	temp.distance =0;
	temp.vertex = s;
	E[0]=temp;
	minheap<DijkElem,DDComp>H(E,1,G->e());
	for(i=0;i<G->n();i++)
	{
		do{
			if(!H.removemin(temp)) return;
			v=temp.vertex;
		}while(G->getMark(v) ==VISITED);
		G->setMark(v, VISITED);
		if(v!=s) AddEdgetoMST(G,V[v],v);
		if(D[v]==INFINITY) return;
		for(w=G->first(v);w<G->n();w=G->next(v,w))
			if(D[w]>G->weight(v,w)){
				D[w]=G->weight(v,w);
				V[w]=v;
				temp.distance=D[w];
				H.insert(temp);
			}
	}
}

int main()
{
	fstream fs;
	fs.open( "Prim.txt", ios::in|ios::out|ios::trunc );
	if(!fs)
	{
		cout<<"open file failed"<<endl;
		return 0;
	}
	
	Graph* G=new Graph(3);
	G->setedge(0,1,1);
	G->setedge(0,2,2);
	G->setedge(1,2,3);
	int *D=new int[G->n()];
	int *V=new int[G->n()];
	for(int j=0;j<G->n();j++)
		V[j]=0;

	initD(D,G,0,3);
	Prim(G,D,V,0);
	cout<<"the pathes are: ";
	for(int i=0;i<G->n();i++)
		cout<<i<<V[i]<<' ';
	cout<<endl;
	delete D;
	delete V;
	delete G;

	G=new Graph(4);
	G->setedge(0,1,1);
	G->setedge(0,2,2);
	G->setedge(0,3,3);
	G->setedge(1,3,4);
	G->setedge(2,3,5);

	D=new int[G->n()];
	V=new int[G->n()];
	for(j=0;j<G->n();j++)
		V[j]=0;
	
	initD(D,G,0,4);
	Prim(G,D,V,0);
	cout<<"the pathes are: ";
	for(i=0;i<G->n();i++)
		cout<<i<<V[i]<<' ';
	cout<<endl;
	delete D;
	delete V;
	delete G;
	cout<<"end of the correctness check"<<endl;

	double average[10]={0};
	for(int nsize=1;nsize<=10;nsize++)
	{
		int index, i;
		int n=NUM*nsize;
		int *forpoint=new int[2*n];
		int *foredge=new int[n];
		Graph *G=new Graph(n);
		for(int times=1;times<=50;times++)
		{
			for (i=0; i<2*n; i++)
				forpoint[i] = i;
			for(i=0;i<n;i++)
				foredge[i]=i;
			
			srand((int)time(0));
			
			for (i=0; i<2*n; i++) {
				index = (int)((float)(2*n-i) * rand() / (RAND_MAX+1.0));
				forpoint[index] = forpoint[2*n-1-i];
			}
			for(i=0;i<n;i++){
				foredge[i] = (int)fmod((float)(n-i) * rand() , (G->n()-1));
			}

			for(int j=0;j<n;j++)
			{
				G->setpoint(j,forpoint[j],forpoint[n+j]);	
			}
			for(j=1;j<n;j++)
			{
				G->setedge(0,j);
			}
			for(j=0;j<n/2;j++)
			{
				G->setedge(foredge[j],foredge[j+n/2]);
			}
			
			int *D=new int[G->n()];
			int *V=new int[G->n()];
			for(j=1;j<G->n();j++)
				V[j]=0;
			initD(D,G,0,G->n());

			double begin=getTime2();
			Prim(G,D,V,0);
			double end=getTime2();  
			double period=end-begin;
			average[nsize-1]=period+average[nsize-1];
			fs<<"n size:"<<n<<"   team "<<times<<"	using time:	"<<period<<endl;
		}
		cout<<"n size:"<<n<<endl;
		average[nsize-1]=average[nsize-1]/100;
		fs<<"******************************************************"<<endl;
		delete forpoint;
		delete foredge;
		delete G;
	}
	for(j=0;j<10;j++)
		fs<<"for n size:"<<(j+1)*NUM<<" the average is: "<<average[j]<<endl;
	fs.close();
	return 0;
}