图（导游图）的创建---------

Question

制作陶瓷学院的校园导游图，游客通过终端可询问： （1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边） 2、要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择游览路线。 （3）画出景点分布图于屏幕上。 3、实现提示 （1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。 （2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。    

Answer 1

参考一下

#include <stdio.h>
#include <stdlib.h>
 
#define OK 1
#define ERROR -1
#define OVERFLOW 0				
#define MAXVER 20				//定义最大定点数
#define MAXINT 200			   	// 无穷大
#define NULL 0
 
typedef char verType;			//定义顶点类型
typedef int status ;
 
typedef struct ver				//关于景点(顶点)信息存放（结构体数组）
{
	char name[20];				//存放景点名称
	char mask;					//存放景点代号
	char intro[20];				//景点简介
    
}Ver[MAXVER];
 
typedef struct					//无向网存放景区信息
{
	Ver  verx;					//定义顶点
    int arcs[MAXVER][MAXVER];	//定义弧
	int vernum,arcsnum;			//定义最大顶点数 和弧
}MGraph;
 
int locate(MGraph G,verType ch) //查找顶点在数组中的下标
{
	int i;
    for(i=0;i<G.vernum&&ch!=G.verx[i].mask;i++);
	return i;
}
 
status createUDN(MGraph &G,int &v)			//创建无向网
{
	int i,j,w,k;
	verType ch1,ch2;
	printf("请输入场所的个数和路径数：格式如2 3\n");
	scanf("%d%d",&G.vernum,&G.arcsnum); 
	fflush(stdin);
	printf("请输入顶点信息\n");
	for(i=0;i<G.vernum;i++)
	{
		printf("\n请输入第%d个景点名称:\n",i+1);
		scanf("%s",&G.verx[i].name);
		fflush(stdin);
		printf("请输入景点代号，用一个字符表示如A\n");
		scanf("%c",&G.verx[i].mask);
		fflush(stdin);
		printf("请对景点简单介绍\n");
		scanf("%s",&G.verx[i].intro);
		fflush(stdin);
	}
	for(i=0;i<G.vernum;i++)
	{
		for(j=0;j<G.vernum;j++)
			G.arcs[i][j]=MAXINT;			//赋初值为无穷大
	}
	printf("请输入场所间距离：格式A B 3\\n \n");
	for(i=0;i<G.arcsnum;i++)
	{
		printf("请输入第%d对值\n",i+1);
		scanf("%c %c %d",&ch1,&ch2,&w);		   //输入顶点符号和权值
		fflush(stdin); 
		k=locate(G,ch1);					   //获得顶点下标
		j=locate(G,ch2);
		G.arcs[k][j]=w;						   //为临界矩阵赋值
		G.arcs[j][k]=G.arcs[k][j];			   //无向图为对称矩阵
	}
	return OK;
}
 
 
void message(MGraph G)						//进行信息查询
{
    char mask;
	printf("请输入要查询景点代号如A\n");
	scanf("%c",&mask);
	fflush(stdin);
		for(int i=0;i<G.vernum;i++)
		{
			if(mask==G.verx[i].mask)
			{
				printf("景点名称：%s\n景点简介：%s",G.verx[i].name,G.verx[i].intro);
				return;
			}
		}
		return;
}
 
 
int search(MGraph G)						//进行最短路径查询
{
	char value1,value2; 
	int i,j;								//存放两个值得下标
	int q;
	int all=0;								//记录经过点的个数
	int lujing[MAXINT][MAXINT];			    //用来 记录路径
	for (int m=0;m<MAXINT;m++)
		for (int n=0;n<MAXINT;n++)
			lujing[m][n]=NULL;
 
	int sub;
	int D[MAXVER],P[MAXVER],min;
	bool final[MAXVER];
	printf("\n请输入两个场所值求其最短距离和路径 如A B\n");
	scanf("%c %c",&value1,&value2);
    i=locate(G,value1);						//获得第一个顶点下标
	j=locate(G,value2);						//获取第二个顶点下标
	sub=i;
	
	for(int v=0;v<G.vernum;++v)				//初始化工作
	{
       final[v]=false;						//从起始点到另外点均未找到最短路径 主要是定义一个集合将访问过的点设置值为true  刚开始集合为空
       D[v]=G.arcs[i][v];					//从其余点到起始点距离(记录是最短距离  到起始点)
 
	}
	D[i]=0;final[i]=true;					//起始点到起始点距离为0 起始点设置为已经访问过
	P[sub]=-1;
 
	
	for(int out=1;out<G.vernum;out++)		//最多扩充n-1个点到已经访问过的点集
	{
       min=MAXINT;
	   for(int w=0;w<G.vernum;w++)			// 在当前未选择点集中选估计距离最小的顶点k
	   {
		   if(!final[w])
			   if(D[w]<min) { q=w; min=D[w]; }			   			   
	   }
	   final[q]=true;						//将最小距离点加入到已经访问过点集中
       P[q]=sub;
	   for( w=0;lujing[q][w]!=NULL;w++){}
	   lujing[q][w]=q;				  		   	   
	   for(int m=0;m<G.vernum;m++)			//调整剩余点到起始点的估计距离
	   {
		   if(!final[m]&&(min+G.arcs[q][m]<D[m]))
		   {
			   D[m]=min+G.arcs[q][m];sub=q;
			   P[m]=sub;
		       for( w=0;lujing[q][w]!=NULL ;w++)
				   lujing[m][w]=lujing[q][w];
			   for(;lujing[m][w]!=NULL;w++)
				   lujing[m][w]=NULL;
		   }
	   }
	   if(q==j)
	   {
		   printf("最短路径为%d\n",D[j]);
		   printf("依次经过景区为:");
				printf("%c   ",value1);
			   for (int c=0;lujing[j][c]!=NULL;c++)
			   {
 
				   printf("%c   ",G.verx[lujing[j][c]].mask);
			   }
	   }
	}
 
 return 0;	
}
 
 
 
 
int main()
{
	MGraph G;
	int v=0;
	int alter;
	printf("请先输入建立校园图所需要的信息：\n\n");
	if(createUDN(G,v))						//创建无向网
	{
		 do
		 {
			 printf("\n\n查询某个景点信息请输入1\n");
			 printf("查询两个景点之间最短距离请输入2\n");
			 printf("退出请输入0\n");
			 scanf("%d",&alter);
			 fflush(stdin);
			 switch(alter)
			 {
				 case 0:return 0; break;
				 case 1: message(G);break;
				 case 2:search(G);break;	
			 }
		}while(alter);
	}
	return 0;
}