setmaxvertices.cpp

普里母算法和克卢氏卡儿的关于求最短路径的无向图算法

#include <iostream>
#include <String>
#include <time.h>

using namespace std;
//#define	DEBUG //add by bighead
#define DEBUG_TIME
#define LOOPS  10000

#include "MinSpanTree.cpp"
#include "MinHeap.cpp"
#include "UFSets.cpp"
#include "SeqList.cpp"

const int MaxNumEdges = 50;//最大边数

#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10;							//最大顶点数
#endif

//using std::istream;

template <class NameType, class DistType> class Graph {			//图的类定义
private:
   SeqList<NameType> VerticesList;//( MaxNumVertices );			//顶点表
   DistType Edge[MaxNumVertices][MaxNumVertices];				//邻接矩阵
   int CurrentEdges;											//当前边数
   int FindVertex ( SeqList<NameType> & L, const NameType & vertex )
     { return L.Find (vertex); }     							//在顶点表L中搜索顶点vertex
   int GetVertexPos ( const NameType & vertex )
     { return FindVertex (VerticesList, vertex ); }
    //给出顶点vertex在图中的位置
public:
   Graph ( const int sz=MaxNumEdges );									//构造函数
   int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); }		//判图空否
   int GraphFull ( ) const { return VerticesList.IsFull ( ) || CurrentEdges ==MaxNumEdges; }
   int NumberOfVertices ( ) { return VerticesList.Length(); }			//返回当前顶点数
   int NumberOfEdges ( ) { return CurrentEdges; }						//返回当前边数
   NameType GetValue ( const int i )									//取顶点i的值, i不合理则返回空
      { return VerticesList.Get(i); }
   DistType GetWeight ( const int v1, const int v2 );					//给出以顶点v1和v2为两端点的边上的权值
   int GetFirstNeighbor ( const int v );								//给出顶点位置为v的第一个邻接顶点的位置
   int GetNextNeighbor ( const int v1, const int v2 );					//给出顶点位置v1的某邻接顶点v2的下一个邻接顶点
   void InsertVertex (  NameType & vertex );							//插入一个顶点vertex, 该顶点没有入边
   void InsertEdge ( const int v1, const int v2, DistType weight );		//插入一条边(v1, v2), 该边上的权值为weight
   void RemoveVertex ( const int v );									//在图中删去顶点vertex和所有与它相关联的边
   void RemoveEdge ( const int v1, const int v2 );						//在图中删去边(v1,v2)
   void Prim ( MinSpanTree &T ) ;
   void Kruskal ( MinSpanTree &T );

   template <class NameType2, class DistType2> 
   friend istream& operator >>(istream&, Graph<NameType2, DistType2>& );
   template <class NameType2, class DistType2> 
   friend ostream& operator <<(ostream&, Graph<NameType2, DistType2>& );
};

template <class NameType, class DistType> Graph<NameType, DistType>::Graph ( 
const int sz ) {
//构造函数
   for ( int i=0; i<sz; i++ )					//邻接矩阵初始化
	 for ( int j=0; j<sz; j++ ) Edge[i][j] = 0;
   CurrentEdges = 0;						//图中当前边数初始化
   #ifdef DEBUG
   		cout << "Graph construct!" << endl;
   #endif
};

template <class NameType, class DistType>
DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2 )
{
//给出以顶点v1和v2为两端点的边上的权值
   if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];
   else return 0;							//带权图中权值为0, 表示无权值
};


template <class NameType, class DistType>
int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {
//给出顶点位置为v的第一个邻接顶点的位置, 如果找不到, 则函数返回-1。
   if ( v != -1 ) {
	 for ( int col=0; col<VerticesList.Length(); col++ ) 
	 	if ( Edge[v][col] > 0 ) return col;
   }
   return -1;
};

template <class NameType, class DistType>
int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2 
) {
//给出顶点v1的某邻接顶点v2的下一个邻接顶点
   if ( v1 != -1 && v2 != -1 )
   {
     for ( int col=v2+1; col<VerticesList.Length(); col++ )
       if ( Edge[v1][col] > 0 ) return col;
   }
   return -1;
};

template <class NameType, class DistType>
void Graph<NameType, DistType>::InsertVertex (  NameType & vertex )		//插入一个顶点vertex, 该顶点没有入边
{
	assert (VerticesList.Insert ( vertex, VerticesList.Length() ));
};

template <class NameType, class DistType>
void Graph<NameType, DistType>:: InsertEdge ( const int v1, const int v2, 
DistType weight )	//插入一条边(v1, v2), 该边上的权值为weight
{
	CurrentEdges++;
	Edge[v1][v2]=weight;
	Edge[v2][v1]=weight;
};


template <class NameType,class DistType>
void Graph<NameType, DistType>::Prim ( MinSpanTree &T ) {
   int NumVertices = VerticesList.Length();				//图中顶点数
   if (NumVertices<=0) return;
   int *lowcost,*nearvex;
   lowcost = new int[NumVertices];				//创建辅助数组
   nearvex = new int[NumVertices];				//创建辅助数组TV
   for ( int i=1; i<NumVertices; i++ ) 
   {
	 if (Edge[0][i]==0) 
	 	lowcost[i]=MAXINT; 
	 else 
	 	lowcost[i] = Edge[0][i];
	 	nearvex[i] = 0;		//顶点0到各边的代价及最短带权路径
   }
   nearvex[0] = -1;							//顶点0加到生成树顶点集合, 用-1表示

   for (int i=1; i<NumVertices; i++ ) 
   { //循环-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]; 
		}
	 if ( v )
	 {	// v==0表示再也找不到要求的顶点了
	   T.addEdge(nearvex[v],v,lowcost[v]);
	   nearvex[v] = -1;						//加入生成树顶点集合
	   for (int j=1; j<NumVertices; j++ )
		 if ( (nearvex[j] != -1) && (Edge[v][j]!=0) && (Edge[v][j] < lowcost[j]) )
		   { 
				lowcost[j] = Edge[v][j];  
		   		nearvex[j] = v; 
			}		//修改
	 }
   }
};


template <class NameType, class DistType>
void Graph< NameType, DistType>::Kruskal ( MinSpanTree &T ) 
{												//克鲁斯卡尔算法
   MSTEdgeNode e;
   MinHeap<MSTEdgeNode> H (CurrentEdges );		//最小堆
   int NumVertices = VerticesList.Length();		//图中顶点个数
   #ifdef DEBUG
   		cout << "Kruskal is in use!" <<endl;
   #endif
   UFSets F (NumVertices);						//连通分量
   for ( int u=0; u<NumVertices; u++ ) 			//建立最小堆的数据
	 for ( int v=u+1; v<NumVertices; v++ )
	   if ( Edge[u][v] != 0 ) {					//插入新边值结点到最小堆中
	   e.tail=u;e.head=v;e.key=Edge[u][v];
		 H.Insert (e);
	   }
   int count = 1;								//生成树边计数
   while ( count < NumVertices ) {				//反复执行, 取n-1条边
	 H.RemoveMin (e );							//从最小堆中退出具最小权值的边
	 int u = F.Find ( e.tail );
	 int v = F.Find ( e.head );					//取两顶点所在集合的根
	 if ( u != v ) {							//不是同一集合, 说明不连通
	   F.Union ( u, v );
	   T.addEdge(e.tail,e.head,e.key);
	   count++;									//合并, 连通它们, 该边加入生成树
	 }
   }
};


template <class NameType, class DistType> 
istream& operator >>(istream& is, Graph<NameType,DistType>& g)
{
   int n,e,k,j;
   NameType head,tail,name;
   DistType weight;
   cout << "Input Vertices num = ";
   is >> n;										//输入顶点个数
   cout << "Vertices Name = " << endl;
   for ( int i=0; i<n; i++)
   {
     is >> name;
     g.InsertVertex ( name );
   }											//依次输入顶点, 插入图中
	
   cout << "Input Edges num = ";	
   is >> e;										//输入边数
   cout << "Edge = <VerticsTail,VerticeHead,Weight>" << endl;
   for (int i=0; i<e; i++) {					//依次输入边信息
	 is >> tail >> head >> weight;				//输入各边
	 k = g.GetVertexPos ( tail );  
	 j = g.GetVertexPos ( head );				//取两顶点位置
	 g.InsertEdge ( k, j, weight );				//插入图中
   }
   return is;

}

template <class NameType, class DistType> 
ostream& operator <<(ostream& strm, Graph<NameType,DistType>& g)
{
	int	edgeNum,vecticesNum;
	edgeNum = g.NumberOfEdges();
	vecticesNum = g.NumberOfVertices();
	strm << "All the Vectics(" << vecticesNum << ") are below: <index,name>\n";
	for(int i=0;i < vecticesNum;i++)
		strm << i <<":"<<g.GetValue(i)<<"\t";
	strm << "\nAll the edges(" << edgeNum << ") are below:<head,tail,weight>\n";
	for(int i=0;i < vecticesNum;i++)
		for(int j=i+1;j < vecticesNum;j++)
			if(g.GetWeight(i,j) != 0)
				strm << "<" << i <<", "<<j<<", "<<g.GetWeight(i,j)<<">\t";
	return strm;
				
}
main()
{
	char p;
	#ifdef DEBUG_TIME
		clock_t start,end;
	#endif	
	int	times = 3;
	while(times)
	{
		cout << "\nPlease make your choice! 1, 2, 3 or 4" << endl;
		cout << "1:Demo 1 " << endl;
		cout << "2:Demo 2 " << endl;
		cout << "3:Construct the graph yourself! " <<endl;
		cout << "4:Quit " << endl;
		cout << "Type q or Q to exit!" << endl;
		cin >> &p;
		switch (p)
		{
			case '1':
				{
					cout << "\nChoice 1:This is in Demo 1 ! "<< endl;
					string iVetStr[7]={"0","1","2","3","4","5","6"};
					Graph<string,int> iGraph(7);
					for(int i=0;i<7;i++)
						iGraph.InsertVertex(iVetStr[i]);
					iGraph.InsertEdge(0,1,28);	
					iGraph.InsertEdge(0,5,10);
					iGraph.InsertEdge(1,2,16);
					iGraph.InsertEdge(1,6,14);
					iGraph.InsertEdge(2,3,12);
					iGraph.InsertEdge(3,4,22);
					iGraph.InsertEdge(3,6,18);
					iGraph.InsertEdge(4,6,24);
					iGraph.InsertEdge(5,4,25);	
					//display the graph
					cout << iGraph <<endl;
					#ifdef DEBUG_TIME
						start = clock();//t.start(); 
					#endif
					MinSpanTree	iMinSpanTreeK(iGraph.NumberOfVertices());
					iGraph.Kruskal(iMinSpanTreeK);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeK_tmp(iGraph.NumberOfVertices());
						iGraph.Kruskal(iMinSpanTreeK_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;  
					#endif
					cout<<iMinSpanTreeK<<endl;
				
					#ifdef DEBUG_TIME
						start = clock();//t.start();
					#endif
					MinSpanTree	iMinSpanTreeP(iGraph.NumberOfVertices());
					iGraph.Prim(iMinSpanTreeP);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeP_tmp(iGraph.NumberOfVertices());
						iGraph.Prim(iMinSpanTreeP_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl; 
					#endif
					cout<<iMinSpanTreeP<<endl;
				}
				break;
				
			case '2':
				cout << "\nchoice 2:This is in Demo 2" << endl;
				{
					string iVetStr[9]={"A","B","C","D","E","F","G","H","I"};
					Graph<string,int> iGraph(9);
					for(int i=0;i<9;i++)
						iGraph.InsertVertex(iVetStr[i]);
					iGraph.InsertEdge(0,1,28);	
					iGraph.InsertEdge(0,5,10);
					iGraph.InsertEdge(1,2,16);
					iGraph.InsertEdge(1,6,14);
					iGraph.InsertEdge(2,3,12);
					iGraph.InsertEdge(3,4,22);
					iGraph.InsertEdge(3,6,18);
					iGraph.InsertEdge(4,6,24);
					iGraph.InsertEdge(5,4,25);	
					iGraph.InsertEdge(5,7,2);
					iGraph.InsertEdge(5,6,15);
					iGraph.InsertEdge(6,8,21);
					iGraph.InsertEdge(8,4,15);
					iGraph.InsertEdge(7,3,25);
					//display the graph
					cout << iGraph <<endl;
					#ifdef DEBUG_TIME
						start = clock();//t.start(); 
					#endif
					MinSpanTree	iMinSpanTreeK(iGraph.NumberOfVertices());
					iGraph.Kruskal(iMinSpanTreeK);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeK_tmp(iGraph.NumberOfVertices());
						iGraph.Kruskal(iMinSpanTreeK_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;  
					#endif
					cout<<iMinSpanTreeK<<endl;
				
					#ifdef DEBUG_TIME
						start = clock();//t.start();
					#endif
					MinSpanTree	iMinSpanTreeP(iGraph.NumberOfVertices());
					iGraph.Prim(iMinSpanTreeP);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeP_tmp(iGraph.NumberOfVertices());
						iGraph.Prim(iMinSpanTreeP_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl; 
					#endif
					cout<<iMinSpanTreeP<<endl;
				}
				break;
				
			case '3':
				cout << "\nChoice 3:Construct the Graph yourself! "<<endl;
				{
					cout << "Begin MaxVertices = " << MaxNumVertices << endl;
					Graph<string,int> iGraph(MaxNumVertices);
					
					cin >> iGraph;
					cout << iGraph <<endl;	
					#ifdef DEBUG_TIME
						start = clock();
					#endif
					MinSpanTree	iMinSpanTreeK(MaxNumVertices);
					iGraph.Kruskal(iMinSpanTreeK);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeK_tmp(MaxNumVertices);
						iGraph.Kruskal(iMinSpanTreeK_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;  
					#endif
					cout<<iMinSpanTreeK<<endl;
					
					#ifdef DEBUG_TIME
						start = clock();
					#endif
					MinSpanTree	iMinSpanTreeP(MaxNumVertices);
					iGraph.Prim(iMinSpanTreeP);
					for(int i=0;i < LOOPS;i++)
					{
						MinSpanTree	iMinSpanTreeP_tmp(MaxNumVertices);
						iGraph.Prim(iMinSpanTreeP_tmp);
					}
					#ifdef DEBUG_TIME
						end = clock();
						cout << "start:" << start << " end:" << end << endl;
						cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl; 
					#endif
					cout<<iMinSpanTreeP<<endl;
				}
				break;
				
			case '4':
				return 1;
				break;
			
			case 'q':
				return 1;
				break;

			case 'Q':
				return 1;
				break;
								
			default:
				times--;
				cout << "\nare you kidding? Please input correctly! "<< times <<" times left!"<<endl;
				break;
		}
	}
	return 0;
}