tu.cpp

测试最小生成树的krim算法,验证这种算法的正确性和时间的快慢。

#include <iostream.h>

const int maxWeight=10000;
const int DefaultVertices=10000;
const int maxEdges=10000;

const int MAXINT = 10000000;
class Graph
{
	friend istream & operator >> (istream & in ,Graph &G);
	friend ostream & operator << (ostream & out,Graph &G);
private:
	int *VerticesList;
	int **Edge;
	int numVertices;
	int numEdges;
	int maxVertices;
public:
	Graph();
	~Graph();
	bool insertVertex(const int vertex);
	bool insertEdge(int v1,int v2,int cost);
	int getVertexPos(int vertex);
	int getValue(int i);
	int getWeight(int v1,int v2);
	int NumberOfVertices();
	int NumberOfEdges();	
	void Prim();
};

Graph::Graph()
{
	maxVertices=DefaultVertices;
	numVertices=0;
	numEdges=0;
	int i,j;
	VerticesList=new int [maxVertices];
	Edge=(int **)new int *[maxVertices];
	for(i=0;i<maxVertices;i++)
		Edge[i]=new int[maxVertices];
	for(i=0;i<maxVertices;i++)
		for(j=0;j<maxVertices;j++)
			Edge[i][j]=(i==j)?0:maxWeight;
};
Graph::~Graph()
{
	delete []VerticesList;
	delete []Edge;
};
int Graph::getVertexPos(int vertex)
{
	for(int i=0;i<numVertices;i++)
		if(VerticesList[i]==vertex)
			return i;
	return -1;
};
int Graph::getValue(int i)
{
	return (i>=0&&i<=numVertices)?VerticesList[i]:NULL;
};
int Graph::getWeight(int v1,int v2)
{
	return (v1!=-1&&v2!=-1)?Edge[v1][v2]:0;
};
int Graph::NumberOfVertices()
{
	return numVertices;
};
int Graph::NumberOfEdges()
{
	return numEdges;
};
bool Graph::insertVertex(const int vertex)
{
	if(numVertices==maxVertices)
		return false;
	VerticesList[numVertices++]=vertex;
	return true;
};
bool Graph::insertEdge(int v1,int v2,int cost)
{
	if(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edge[v1][v2]==maxWeight)
	{
		Edge[v1][v2]=Edge[v2][v1]=cost;
		numEdges++;
		return true;
	}
	else
		return false;
};
istream & operator >> (istream &in ,Graph &G)
{
	int edges,vertices,i,j,k;
	int start,end,weight;
	in>>vertices>>edges;
	for(i=1;i<=vertices;i++)
	{
		G.insertVertex(i);
	}
	i=0;
	while(i<edges)
	{
		in>>start>>end>>weight;
		j=G.getVertexPos(start);
		k=G.getVertexPos(end);
		if(j==-1||k==-1)
			cout<<"input error!"<<endl;
		else
		{
			G.insertEdge(j,k,weight);
			i++;
		}
	}
	return in;
};

ostream& operator <<(ostream &out,Graph &G)
{
	int i,j,vertices,edges;
	int start,end,weight;
	vertices=G.NumberOfVertices();
	edges=G.NumberOfEdges();
	out<<vertices<<","<<edges<<endl;
	for(i=0;i<vertices;i++)
	{
		for(j=i+1;j<vertices;j++)
		{
			weight=G.getWeight(i,j);
			if(weight>0 && weight<maxWeight)
			{
				start=G.getValue(i);
				end=G.getValue(j);
				out<<"("<<start<<","<<end<<","<<weight<<")"<<endl;
			}
		}
	}
	return out;
};

void Graph::Prim ( ) {
	int *lowcost,*nearvex;
	int sum=0;
    lowcost=new int[numVertices];			
    nearvex=new int[numVertices];			
    for (int i=1;i<numVertices;i++) {
        lowcost[i]=Edge[0][i];	    //顶点0到各边的代价
        nearvex[i]=0;	            //及最短带权路径
    }
	nearvex[0]=-1;					//顶点0加到生成树顶点集合
	int count = 0;					//生成树边值数组存放指针
	for(i=1;i<numVertices;i++)		//循环n-1次, 加入n-1条边
	{   			
		int min=MAXINT;  
		int v=0;		
		for(int j=0;j<numVertices;j++)	
		{
			if (nearvex[j]!=-1 && lowcost[j]<min )
			{
				v=j;				//求生成树外顶点到生成树内顶点具有最小
				min=lowcost[j];		//权值的边, v是当前具最小权值的边的位置
			}  
		}
		if(v!=0)
		{						//v==0表示再也找不到要求的顶点了
			count++;	        //向生成树边值数组内存放   
			sum+=lowcost[v];	
		    nearvex[v]=-1;		//作该边已加入生成树标记
			for (j=1;j<numVertices;j++)
			{
				if (nearvex[j]!=-1 && Edge[v][j]<lowcost[j] )     //j不在生成树中
				{    //需要修改
					lowcost[j] = Edge[v][j];
					nearvex[j] = v; 
				}
			}
		}
	}
	int c=0;
//	cout<<sum<<endl;
	for(int k=1;k<numVertices;k++)
		c+=lowcost[k];
	cout<<c<<endl;
}

int main()
{
	Graph G;

	cin>>G;
//	cout<<G;
	G.Prim();
	return 0;
}
/*test	
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6

*/