graph.h

公园导图算法

# ifndef Graph_h

# include <iostream.h>
# include <stdlib.h>

# define MAXNUM 1000
# define MAXSIZE 100

template <class Type> struct Edgenode  //节点的定义
{
	int head;
	int tail;
	Type cost;
};

template <class Type> class Minspantree
{
	public:
		Minspantree(int sz=MAXSIZE);
		int Insert(Edgenode <Type> &e);
        Edgenode <Type>& Getvalue(int i) { return edgevalue[i];}
		friend ostream & operator << (ostream &out,Minspantree<Type> &T);
		int Getsize() {return Maxsize;}
	protected:
		int Maxsize;
		int current;
		Edgenode <Type> *edgevalue;
};

template <class Type> class Graph
{
	public:
		Graph(int sz1=Maxsize,int sz2=Maxsize);
		int Insert(Edgenode <Type> &e);
        Type Getedge (int i,int j) {return Edge[i][j];}
        friend ostream& operator <<(ostream &out,Graph <Type> &a);
		~Graph();
		void Shortestpath(int,int);
		int Choose(int,int,int);
		void Prim (Minspantree <Type> &T,int n);
	protected:
		int edgenum,vertnum;   //边数和点数
		Type Edge[MAXSIZE][MAXSIZE];
		int *path;             //路径数组
		Type *dist;
		int *S;
};

//最小生成树的函数实现
template <class Type> Minspantree<Type>::Minspantree(int sz)
{
    current=0;
    Maxsize=sz;
	edgevalue=new Edgenode <Type> [sz];
}

template <class Type> int Minspantree <Type>::Insert(Edgenode <Type> &item)
{
	if(current>Maxsize-1) {cout<<"最小生成树已经满，不能插入"<<endl;return 0;}
	else{
        edgevalue[current].head=item.head;
        edgevalue[current].tail=item.tail;
        edgevalue[current].cost=item.cost;
	    current++;
	    return 1;
	}
}

template <class Type> ostream & operator << (ostream &out,Minspantree <Type> &T)  //数组的输出
{
	out<<"景点"<<T.Getvalue(0).head+1<<" -> "<<"景点"<<T.Getvalue(0).tail+1;
	for(int i=1;i<=T.Getsize()-1;i++) out<<" -> "<<"景点"<<T.Getvalue(i).tail+1;       
	out<<endl;
	return out;
}

//图有关成员函数的实现

template <class Type> Graph <Type>::Graph(int sz1,int sz2)
{
	if(sz1==0||sz2==0) {cout<<"顶点和边数不能为零!!"<<endl;exit(1);}
	else if(sz1>MAXSIZE) {cout<<"顶点不能超过1000"<<endl;exit(1);}
	else{
		edgenum=sz2;vertnum=sz1;		
		for(int i=0;i<sz1;i++)
			for(int j=0;j<sz1;j++)
			{
				if(i==j) Edge[i][j]=0;
				else Edge[i][j]=MAXNUM;
			}
		dist=new Type[sz1];
	    path=new int[sz1];
	    S=new int[sz1];
	}
}

template <class Type> int Graph <Type>::Insert(Edgenode <Type> &e)
{
	Edge[e.head-1][e.tail-1]=e.cost;
	Edge[e.tail-1][e.head-1]=e.cost;
	return 1;
}

template <class Type> ostream& operator <<(ostream &out,Graph <Type> &a)  //输出整个图
{
	for(int i=0;i<vertnum;i++)
		for(int j=0;j<vertnum;j++)
		{
			out<<i+1<<" "<<j+1<<" "<<Getedge(i,j)<<"   "<<endl;
		}
}

template <class Type> Graph<Type>::~Graph()   //析构辅助数组
{
	delete []path;
	delete []dist;
	delete []S;
}

//迪克斯特拉算法求shortestpath
template <class Type> void Graph<Type> ::Shortestpath ( int n, int v)
{
        for ( int i=0; i<n; i++) 
		{				
        dist[i] = Edge[v][i];     //dist和path数组初始化
        S[i] = 0;					
        if ( i != v && dist[i] < MAXNUM ) 	path[i] = v;		
        else path[i] = -1;				        
		}  
       S[v] = 1;  dist[v] = 0;	//顶点v加入顶点集合       
       for ( i = 0; i < n-1; i++ ) //选择当前不在集合S中具有最短路径的顶点u
	   {			
           Type min = MAXNUM;  
		   int u = v;
           for ( int j = 0; j < n; j++ )		
	           if ( !S[j] && dist[j] < min ) 
			   { 
				   u = j;   
				   min = dist[j]; 
			   }
          S[u] = 1;	                //将顶点u加入集合S,表示它已经在最短路径上
          for ( int w = 0; w < n; w++ )    //修改 
	       if ( !S[w] && Edge[u][w] < MAXNUM &&dist[u] + Edge[u][w] < dist[w] ) 
		   {
	       dist[w] = dist[u] + Edge[u][w]; 
	       path[w] = u;
		   }
	   }

}

template <class Type> int Graph <Type>::Choose(int n,int v,int t)
{
	Shortestpath(n,v-1);
	if(t!=0)                                //输出任意两个景点的长度
	{
           cout<<" 景点"<<v<<" -> 景点"<<t<<" 的最短路径 : ";
           Type length=dist[t-1];
           int k=1,p=t-1;
           while(path[p]!=-1)				 //检测最短路径上的点个数 
		   {
				k++;
				p=path[p];
		   }
		   int m=k;
		   int *a=new int[m];                //创建辅助数组存储景点
		   p=t-1;
		   a[k-1]=t-1;
		   while(path[p]!=-1)
		   {
				k--;
				a[k-1]=path[p];
				p=path[p];
		   }
		   for( int j=0;j<m-1;j++)
				cout<<"景点"<<a[j]+1<<" -> ";
		   cout<<"景点"<<a[j]+1<<" , ";
		   cout<<"路径全长为"<<length<<endl;
		   return 1;
	   }
	else if(t==0)
	{
			for(int j=1;j<=vertnum;j++)
			{
				if(j!=v) Choose(n,v,j);
			}
			return 1;
	}
	return 0;
}

template <class Type> void Graph <Type>::Prim (Minspantree <Type> &T,int n)  //prim算法求最小生成树
{
    int NumVertices = n;	 //图中顶点数
    Type *lowcost = new Type[NumVertices];			
    int *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 = 1;          //生成树边值数组存放指针
    Edgenode <Type> e;    //最小生成树结点辅助单元
    for ( i = 1; i < NumVertices; i++ ) 
	{   //循环n-1次, 加入n-1条边			
       Type min = MAXNUM;  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 ) 
	   {   //v==0表示再也找不到要求的顶点了  //向生成树边值数组内存放                  
           if(count==1)
		   {  
			   e.head=0;
		       count++;
		   }
		   else
               e.head = nearvex[v];
		   e.tail = v;  
           e.cost = lowcost[v];   
           T.Insert (e);           //选出的边加入生成树
           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;
			   }
      }
   }
}

# endif