hah.cpp

基于Prim算法的公路交通设计系统

#include<iostream.h>
#include<stdlib.h>
#define inf 2000
#define maxint 5
class Prim           //类Prim
{
protected:
unsigned int vex;    //城镇个数
unsigned int closest[maxint];    //i在s中的邻接顶点
unsigned int lowcost[maxint];    //城镇i和closest[i]间的最短路程
bool s[maxint];                  //标识城镇i是否进入集合s
unsigned int AdjMatrix[maxint+1][maxint+1];  //存放邻接矩阵的数组
public:
Prim(unsigned int t);
void MiniSpanTree_PRIM();    //Prim算法
};

Prim::Prim(unsigned int t)     //对象初始化
{	
	vex=t;
	unsigned int choice=1,i=1,j,m=0;

	cout<<"1:输入城市代号及路程."<<endl;

	 for(i=1;i<=maxint;i++)
	 for(unsigned int j=1;j<=maxint;j++)
		   {AdjMatrix[i][j]=AdjMatrix[j][i]=0;}
	          m=vex*(vex-1)/2;
              cout<<"总共需输入"<<m<<"组"<<endl;
			  cout<<"城镇代号i应该符合i>=1且i<="<<vex<<endl;
			  cout<<"请依次输入两个城市代号及它们间的路程"<<endl;
    for(int k=0;k<m;k++)
    {
io:  cin>>i>>j;
	  cin>>AdjMatrix[i][j];
	  if(i<1||i>vex||j<1||j>vex)
	  {	cout<<"输入有误，请重新输入！"<<endl;
goto io;
	  }
	  else
      AdjMatrix[j][i]=AdjMatrix[i][j];
	  cout<<"已经输入"<<k+1<<"次，还可输入"<<m-k-1<<"次"<<endl;
    }
	    for( i=1;i<=maxint;i++)
        for(int j=1;j<=maxint;j++)
		{
		if(AdjMatrix[i][j]==0)
		AdjMatrix[j][i]=AdjMatrix[i][j]=inf;	
		}
		 cout<<"各城镇间的路程情况为"<<endl;

	for( i=1;i<=vex;i++)
        for(int j=1+i;j<=vex;j++)
		{
			if(AdjMatrix[i][j]!=2000)
	     cout<<i<<"*****"<<AdjMatrix[i][j]<<"*****"<<j<<endl<<endl;
	        else
		  cout<<i<<"*****"<<"无路"<<"*****"<<j<<endl<<endl;
	      
		}
	 
  cout<<"这"<<vex<<"个城市之间修公路的最佳路线为:"<<endl;
  cout<<"起始点"<<"  "<<"路程"<<"  "<<"中止点"<<"     "<<"总路程"<<endl;
  
}
void Prim::MiniSpanTree_PRIM()     //Prim算法核心的实现
{
	unsigned int total=0;
    s[1]=true;
    for(int i=2;i<=vex;i++)
    {
    lowcost[i]=AdjMatrix[1][i];
    closest[i]=1;
   s[i]=false;
    }
    for(int m=1;m<vex;m++)
    {
     unsigned int min=inf;
     int j=1;
     for(int k=2;k<=vex;k++)
        if((lowcost[k]<min)&&(!s[k]))
		{
         min=lowcost[k];
         j=k;
		}
     	total+=lowcost[j];
    
	 cout<<"****"<<j<<"****"<<lowcost[j]<<"******"<<closest[j]<<"********"<<total<<endl;
     s[j]=true;
        for(int p=2;p<=vex;p++)
         if((AdjMatrix[j][p]<lowcost[p])&&(!s[p]))
		 {
	      lowcost[p]=AdjMatrix[j][p];closest[p]=j;
		 }
	}

} 

int main()                       //主函数
{  
unsigned int v=1;

io:
while(v!=0)
{
    cout<<"请输入城市个数v（v值代表城市代号） 注意v>=2且v<="<<maxint-1<<endl;
	cin>>v;
	if(v<2||v>maxint-1)
	{if(v==0)
	v=v+1;
	goto io;
	}
    Prim p(v);
    p.MiniSpanTree_PRIM();
	 cout<<"若重新输入，请输入1："<<endl;
	cout<<"否则输入0："<<endl;
    cin>>v;
	if(v<2||v>maxint-1)
		goto io;
}
  	return 0;

}