bupt_view.cpp

一个简单的校园景点程序

4#include<iostream.h>
const vtxnum=64;   //图的最大顶点数 
struct graphtp{
          int  vernum;                 //景点个数
	      char vexs[vtxnum];           //景点名称(字母)
		  int  arcs[vtxnum][vtxnum];   //景点间路径信息的邻接矩阵
};
struct pathtp{                         //(栈)路径类型
          char data[vtxnum][vtxnum][vtxnum];//路径
          int top[vtxnum][vtxnum];          //
};
void create(graphtp &image)
{
	 cout<<"please input the number of 景点\n";
	 cin>>image.vernum;                  //读入景点个数
	 cout<<"please input the name of the "<<image.vernum<<" 景点(用一个字母表示)\n"; //输入景点名称(字母)
     for(int k=1;k<=image.vernum;k++)
		 cin>>image.vexs[k];           
	 for(int i=1;i<=image.vernum;i++)                //初始化邻接矩阵
		 for(int j=1;j<=image.vernum;j++)
			 image.arcs[i][j]=0;
	 cout<<"please input the adjacent matrix\n"      //输入邻接矩阵
		 <<"if there were no path between two vertexes  then input number\"100\"\n"
		 <<"                                            else input the reality number\n";
		 for(int h=1;h<=image.vernum;h++)
			 for(int l=1;l<=image.vernum;l++)
				 cin>>image.arcs[h][l];

}
void floyd(graphtp image,int distance[vtxnum][vtxnum],pathtp &path) // 用弗洛伊德计算最短路经
{
     for(int i=1;i<=image.vernum;i++)
		 for(int j=1;j<=image.vernum;j++)
		 {
			 distance[i][j]=image.arcs[i][j];     //把原始邻接矩阵存入初始路径长度  
			 if(distance[i][j]<=100)              //当路径长度小于MAX时，将此路径储存
			 {
				 path.data[i][j][1]=image.vexs[i];
				 path.data[i][j][2]=image.vexs[j];
				 path.top[i][j]=2;
			 }
		 }
     for(int k=1;k<=image.vernum;k++)
		 for(int i=1;i<=image.vernum;i++)
		     for(int j=1;j<=image.vernum;j++)
			 {
				 if((distance[i][k]+distance[k][j])<distance[i][j]) //当i经k到j的路径长度小于i到j的直接路径长度
				 {                                                  //修改路径长度并修改路径
					 distance[i][j]=distance[i][k]+distance[k][j];
                     for(int p=path.top[i][j];p>=(path.top[i][j]-1);p--)  //用栈储存路径
						 path.data[i][j][p+1]=path.data[i][j][p];
					 path.data[i][j][path.top[i][j]]=image.vexs[k];
				     path.top[i][j]++;
				 }
			 }
}
void write(graphtp image)  //用一般方法输出图的信息，以检验邻接矩阵的图的建立是否成功
{
	 
	cout<<"the 景点 are\n";
	 for(int i=1;i<=image.vernum;i++)
		 cout<<image.vexs[i]<<"  ";
	 cout<<endl;
	 cout<<"the adjacent matrix of the graph 景点 is\n";
	 for(int h=1;h<=image.vernum;h++)
			 for(int l=1;l<=image.vernum;l++)
			 {
				 cout<<image.arcs[h][l]<<"  ";
			     if (l==image.vernum)  cout<<endl;
			 }
	 cout<<endl;
}
void write_floyd(graphtp image,int distance[vtxnum][vtxnum],pathtp &path)
{    //输出图的最短路径及其长度
    int c=1;   //用“c”来表示第c个路径
	for(int i=1;i<=image.vernum;i++)
		     for(int j=1;j<=image.vernum;j++)
			    if ((distance[i][j]<100)&&distance[i][j]>0) //当路径长度小于MAX、大于0时，输出此路径
				{
			        cout<<"the "<<c<<" shortest path is\n";
			    	for(int p=1;p<=path.top[i][j];p++)
					     cout<<path.data[i][j][p]<<" ";
			    	c++;
			    	cout<<endl;
				    cout<<"and the length of the path is "<<distance[i][j]<<endl;//输出此路径的长度
			    	cout<<endl;
				}
}
void main()
{
     graphtp graph;
	 pathtp path;
	 int length[vtxnum][vtxnum];
	 create(graph);
	 write(graph);
	 floyd(graph,length,path);
	 write_floyd(graph,length,path);
}