(旅游行业)数据结构旅游区导航图课程设计
《数据结构课程设计》报告
题目 旅游区导游图 专业 计算机科学与技术 班级 （2）班 学生 ###
13旅游区导游图
题目内容 问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m 实现要求： ⑴旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。 ⑵相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。 ⑶景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。 ⑷景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单 路径及距离。 ⑸最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。 ⑹设计一个菜单，上述操作要求都作为菜单中的主要菜单项。 ⒈ 本人完成的工作 完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。 ⒉ 所采用的数据结构 邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义） 邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义） 数据结构的定义 //邻接矩阵结构体 typedefstruct {charvex1,vex2;/*弧或边所依附的两个顶点*/ intArcVal;/*弧或边的权值*/ }ArcType;/*弧或边的结构定义*/ typedefstruct { intvexnum,arcnum;/*图的当前顶点数和弧数*/ charvexs[MAXVEX];/*顶点向量*/ intadj[MAXVEX][MAXVEX]; }MGraph;/*图的结构定义*/ //邻接链表结构体 typedefstructANode//弧的结点结构类型 {intadjvex;//该弧的终点位置 intinfo;//该弧的相关信息,这里用于存放权值 structANode*nextarc;//指向下一条弧的指针 }ArcNode; typedefstructVnode//邻接表头结点的类型 { chardata;//顶点信息 ArcNode*firstarc;//指向第一条弧 }VNode; typedefstruct { VNodeAdjList[MAXVEX]; intvexnum,arcnum;//图中顶点数n和边数e }ALGraph;//图的邻接表类型 ⒊ 所设计的函数 对于每个主要函数必须给出所采用的算法思想和程序框图； 邻接矩阵和邻接链表初始化函数 MGraph*Init_MGraph() /*图的初始化*/ { MGraph*G; G=(MGraph*)malloc(sizeof(MGraph)); G->vexnum=0;G->arcnum=0;/*初始化顶点数、边数*/ return(G); } ALGraph*Init_ALGraph() /*图的初始化*/ { ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); G->vexnum=0; G->arcnum=0;/*初始化顶点数*/ return(G); } 图中顶点定位的函数，判断顶点是否重复输入了 intLocateVex(MGraph*G,charvp) /*图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值*/ { intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k); return(-1);/*图中无此顶点*/ } N NY Y 往图中增加顶点的函数 voidAddVertex(MGraph*G,charvp) /*往图的顶点数组中增加顶点*/ { intk,j; if(G->vexnum>=MAXVEX) printf(\"图中顶点数已达到最多!\\n\"); else { if(LocateVex(G,vp)==-1) { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j G->adj[j][k]=INFINITY; G->adj[k][j]=INFINITY; /*是带权的有向图或无向图*/ } } } } N Y NY 往图的邻接矩阵中添加边(弧) voidAddArc(MGraph*G,ArcType*arc) /*往图的邻接矩阵中添加边(弧)*/ { intk=0,j=0; k=LocateVex(G,arc->vex1); j=LocateVex(G,arc->vex2); if(k==-1||j==-1) printf(\"边或弧的顶点不存在，错误!\\n\"); else { G->arcnum++; G->adj[k][j]=arc->ArcVal; G->adj[j][k]=arc->ArcVal; 结束 新增加一个顶点 给k赋值=顶点总数 判断顶点数目是否已经超过最大值 开始 调用函数LocateVex，判断顶点是否有重复 把这个点跟其他所有点建立关系，为INFINITY，表示不存在连通关系 /*是无向图或带权的无向图,需对称赋值*/ } } 输出图的顶点矩阵和邻接矩阵 voidoutput_graphic(MGraph*G) /*输出图的顶点矩阵和邻接矩阵*/ { intk,j; printf(\"图的顶点如下：\\n\"); for(k=0;k printf(\"图的邻接矩阵如下：\\n\"); for(k=0;k for(j=0;j printf(\"%4d\printf(\"\\n\\n\"); } 输出第k个顶点 判断k是否小于顶点总数 k=0 k=0 } YN YN Y 以邻接矩阵作为图的存储结构建立图 MGraph*create_graph() /*以邻接矩阵作为图的存储结构建立图*/ { charinchar[100],enchar[100],fvex,lvex; intcount=0; intweight; MGraph*G; ArcType*arc; printf(\"首先进行图的初始化!!\\n\\n\"); G=(MGraph*)malloc(sizeof(MGraph)); G=Init_MGraph(); arc=(ArcType*)malloc(sizeof(ArcType)); printf(\"\\n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：\\n\"); while(1) { scanf(\"%s\输入第一个顶点，?结束*/ if(fvex=='?')break; else { AddVertex(G,fvex); scanf(\"%s\scanf(\"%d\输入第二个顶点和权值*/ arc->vex1=fvex;arc->vex2=lvex; arc->ArcVal=weight;AddArc(G,arc); printf(\"\\n请继续输入下一条边(或弧)!!\\n\"); } } return(G); } 将邻接矩阵g转换成邻接表G ALGraph*MGraphToALGraph(MGraph*g,ALGraph*G) { inti,j,n=g->vexnum;//n为顶点数 ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); G->arcnum=g->arcnum; G->vexnum=g->vexnum; for(i=0;i G->AdjList[i].firstarc=NULL; for(i=0;i if(g->adj[i][j]!=INFINITY)//邻接矩阵的当前元素不为 { p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*p G->AdjList[j].data=g->vexs[j]; p->adjvex=g->vexs[j]; p->info=g->adj[i][j]; p->nextarc=G->AdjList[i].firstarc;//将*p链到链表后 G->AdjList[i].firstarc=p; } } returnG; } 邻接链表的输出 voidoutput_graphic_c(MGraph*g,ALGraph*G) 把顶点总数赋值给n { inti; ArcNode*p; 把邻接矩阵的边总数赋值给邻接链表的边总数 开始 把邻接矩阵的顶点总数赋值给邻接链表的顶点总数 用循环结构把每一个顶点的头指针初始化 for(i=0;i printf(\"%c\p=G->AdjList[i].firstarc; while(p!=NULL) { printf(\"%s\ printf(\"(%c,%d)\p=p->nextarc; } printf(\"\\n\\n\"); } } 相邻景点查询并输出 voidoutput_Find_ALGraph(ALGraph*G) {/*相邻景点查询并输出*/ intj; ArcNode*p; printf(\"请输入你要查询的景点(下标值):\\n\"); scanf(\"%d\ p=G->AdjList[j].firstarc; while(p) { printf(\"景点%c到景点%c的距离是%d(该两个景点之间有直接的道路相通)\\n\p=p->nextarc; } printf(\"\\n\\n\"); } 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。 voidDijkstra_One(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]) {//带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre intw; intS[30],i,j,k,p,min; printf(\"你所要开始查询的景点是:%c\\n\for(i=0;i distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i] S[v0]=1;//顶点v0已加入到集合S中 for(i=0;i min=INFINITY; for(j=0;j if(!S[j]&&distance[j] S[k]=1;///将找到的顶点加入到集合S中 for(w=0;w distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf(\"查询结果:\\n\"); for(j=0;j printf(\"从景点%c到景点%c\p=pre[j]; printf(\"的最短距离是:%d\printf(\"途中经过的景点有:\"); while(p!=-1) { printf(\"%c\p=pre[p]; } printf(\"\\n\"); } elseif(j!=v0) printf(\"\\n%c到%c:nopath\} N Y 定义最短路径的终点集数组S 开始 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路输入要查询景点的下标值 径及距离。 用循环结构实现各数组的初始化 置S={v0} voidDijkstra_Two(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]){ //带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre intw; intS[30],i,j,k,p,min,d; printf(\"你所要开始查询的开始景点是:%c\\n\\n\for(i=0;i distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i] min=INFINITY; for(j=0;j if(!S[j]&&distance[j] min=distance[j]; k=j; } } S[k]=1;///将找到的顶点加入到集合S中 for(w=0;w distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf(\"输入你要查询的另外一个景点(下标值):\"); scanf(\"%d\ printf(\"你要查询的另外一个景点是:%c\\n\printf(\"\\n查询结果:\\n\");//输出结果 if(pre[d]!=-1) { printf(\"从景点%c到景点%c\p=pre[d]; printf(\"的最短距离是:%d\ printf(\"途中经过的景点有:\"); while(p!=-1) { printf(\"%c\p=pre[p]; } printf(\"\\n\"); } } 定义最短路径的终点集数组S 开始 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，输入要查询景点的下标值 该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。 用循环结构实现各数组的初始化 voiddfs_path(ALGraph*g,intsrc,intcur,intvis[],GPath*cur_path,GPath*min_path) { if(vis[src]) { if(cur_path->count==g->vexnum) { if(cur_path->value memcpy(min_path,cur_path,sizeof(GPath));/*由cur_path所指内存区域复制sizeof(GPath)个字节到min_path所指内存区域*/ 置S={v0} return; } } return; } ArcNode*node=g->AdjList[cur].firstarc; for(;node!=NULL;node=node->nextarc)/*起始条node=g->AdjList[cur].firstarc*/ { charadj=node->adjvex; intindex=LocateVex(g,adj); if(vis[index]==0) { cur_path->vertex[cur_path->count++]=index; cur_path->value+=node->info; vis[index]=1; dfs_path(g,src,index,vis,cur_path,min_path); cur_path->count--; cur_path->value-=node->info; vis[index]=0; 开始 } } 用循环结构复制cur_pat的内存到min_path 把邻接表数组的头指针赋值给node 件为 } YN NY voidbest_path(ALGraph*g,intsrc) { intvis[MAXVEX]; memset(vis,0,sizeof(vis)); GPathcur_path,min_path; memset(&cur_path,0,sizeof(GPath));/*将cur_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向cur_path的指针。*/ memset(&min_path,0,sizeof(GPath));/*将min_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向min_path的指针。*/ min_=INFINITY; dfs_path(g,src,src,vis,&cur_path,&min_path); if(min_!=INFINITY) { inti=0; printf(\"\\n最佳旅游路线景点下标值是:\\n\"); for(i=0;i printf(\"\\n\"); printf(\"\\n最佳旅游路线景点是:\\n\"); for(i=0;i printf(\"\\n\"); }else { printf(\"建立的图中没有最佳路径\\n\"); } } 主函数 voidmain() { intn,opse,v0,i; intdistance[MAXVEX],pre[2*MAXVEX],path[MAXVEX]; ALGraph*G; MGraph*M; do {printf(\"\\n\\n请选择对图的操作要求:\\n\\n\"); for(n=0;n<=30;n++) printf(\"*\"); printf(\"\\n*\"); printf(\"1----建立图的邻接矩阵\"); printf(\"2----图的邻接矩阵的输出\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"3----图的邻接链表的输出\"); printf(\"4----相邻景点查询\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"5----从某点出发到另外所有点最短简单路径及距离\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"6----两个景点之间的最短距离(下标值)\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"7----最佳路径\"); printf(\"8----退出\"); printf(\"*\\n\"); for(n=0;n<=30;n++) printf(\"*\"); printf(\"\\n\\n\"); do {scanf(\"%d\}while(opse<1||opse>8); switch(opse) { case1: {M=(MGraph*)malloc(sizeof(MGraph)); M=create_graph(); printf(\"\\n\\n\"); break; } case2: {printf(\"\\n您所建立的图是：\\n\"); output_graphic(M); break; } case3: {printf(\"图G的邻接矩阵转换成邻接表:\\n\"); G=MGraphToALGraph(M,G); output_graphic_c(M,G); break; } case4: { printf(\"\\n相邻景点是：\\n\"); output_Find_ALGraph(G); break; } case5: { printf(\"\\n最短简单路径及距离是：\\n\"); scanf(\"%d\ Dijkstra_One(G,M,v0,distance,pre); break; } case6: { printf(\"两个景点之间的最短距离(下标值):\"); scanf(\"%d\ Dijkstra_Two(G,M,v0,distance,pre); break; } case7: { printf(\"最佳路径(下标值):\"); Dijkstra(M,0,distance,path); printf(\"从结点%c到其他各结点的最短距离为:\\n\for(i=1;i printf(\"到结点%c的最短距离为%d:\\n\printf(\"从结点%c到其他各结点最短路径的前一结点为:\\n\for(i=1;i printf(\"到结点%c的前一结点为%c:\\n\break; } } }while(opse!=8); } 开始 ……… 请选择对图的操作要求 ……… ⒋ 每个题目都必须有运行时的输入数据（随机产生的数据要求输出显n=0 n<=30？ 示），运行的输出结果。 建立邻接矩阵： 邻接矩阵输出： 邻接链表输出： 相邻景点查询： 从某点出发到另外所有点最短简单路径及距离： 两个景点之间的最短距离： 最佳路径： ⒌ 每个函数中应给出尽可能详细的中文注释。（源程序-全） #include\"stdio.h\" #include\"malloc.h\" #include\"string.h\" #defineINFINITY32767/*最大值∞*/ /*根据图的权值类型，分别定义为最大整数或实数*/ #defineMAXVEX30/*最大顶点数目*/ //邻接矩阵结构体 typedefstruct {charvex1,vex2;/*弧或边所依附的两个顶点*/ intArcVal;/*弧或边的权值*/ }ArcType;/*弧或边的结构定义*/ typedefstruct { intvexnum,arcnum;/*图的当前顶点数和弧数*/ charvexs[MAXVEX];/*顶点向量*/ intadj[MAXVEX][MAXVEX]; }MGraph;/*图的结构定义*/ typedefstructPath { intvertex[MAXVEX]; intvalue; intcount; }GPath; //邻接链表结构体 typedefstructANode {//弧的结点结构类型 intadjvex;//邻接点在头结点数组中的位置(下标) intinfo;//该弧的相关信息,这里用于存放权值 structANode*nextarc;//指向下一条弧的指针 }ArcNode; typedefstructVnode//邻接表头结点的类型 { chardata;//顶点信息 ArcNode*firstarc;//指向第一条弧 }VNode; typedefstruct { VNodeAdjList[MAXVEX];//邻接表数组 intvexnum,arcnum;//图中顶点数n和边数e }ALGraph;//图的邻接表类型 MGraph*Init_MGraph() /*图的初始化*/ { MGraph*G; G=(MGraph*)malloc(sizeof(MGraph)); G->vexnum=0;G->arcnum=0;/*初始化顶点数、边数*/ return(G); } ALGraph*Init_ALGraph() /*图的初始化*/ { ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); G->vexnum=0; G->arcnum=0;/*初始化顶点数*/ return(G); } intLocateVex(MGraph*G,charvp) /*图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值*/ { intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k); return(-1);/*图中无此顶点*/ } intLocateVexx(ALGraph*G,charvp)/*图的顶点定位（图的顶点定位实际上是确定一个顶点在AdjList数组中的某个元素的data域内容。）*/ { intk; for(k=0;k return(k);/*如果存在此顶点返回顶点数组下标值*/ return(-1);/*如果没有则返回-1(图中无此顶点)*/ } voidAddVertex(MGraph*G,charvp) /*往图的顶点数组中增加顶点*/ { intk,j; if(G->vexnum>=MAXVEX) printf(\"图中顶点数已达到最多!\\n\"); else { if(LocateVex(G,vp)==-1)//图中无此顶点 { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j G->adj[j][k]=INFINITY; G->adj[k][j]=INFINITY; /*是带权的有向图或无向图*/ } } } } voidAddArc(MGraph*G,ArcType*arc) /*往图的邻接矩阵中添加边(弧)*/ { intk=0,j=0; k=LocateVex(G,arc->vex1); j=LocateVex(G,arc->vex2); { G->arcnum++; G->adj[k][j]=arc->ArcVal; G->adj[j][k]=arc->ArcVal; /*是无向图或带权的无向图,需对称赋值*/ } } voidoutput_graphic(MGraph*G) /*输出图的顶点矩阵和邻接矩阵*/ { intk,j; printf(\"图的顶点如下：\\n\"); for(k=0;k printf(\"图的邻接矩阵如下：\\n\"); for(k=0;k for(j=0;j printf(\"%4d\ printf(\"\\n\\n\"); } } MGraph*create_graph() /*以邻接矩阵作为图的存储结构建立图*/ { charinchar[100],enchar[100],fvex,lvex; intcount=0; intweight; MGraph*G; ArcType*arc; printf(\"首先进行图的初始化!!\\n\\n\"); G=(MGraph*)malloc(sizeof(MGraph)); G=Init_MGraph(); arc=(ArcType*)malloc(sizeof(ArcType)); printf(\"\\n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：\\n\"); while(1) { scanf(\"%s\输入第一个顶点，?结束*/ if(fvex=='?')break; else { AddVertex(G,fvex); scanf(\"%s\输入第二个顶点和权值*/ scanf(\"%d\ arc->vex1=fvex;arc->vex2=lvex; arc->ArcVal=weight;AddArc(G,arc); printf(\"\\n请继续输入下一条边(或弧)!!\\n\"); } } return(G); } //将邻接矩阵g转换成邻接表G ALGraph*MGraphToALGraph(MGraph*g,ALGraph*G) { inti,j,n=g->vexnum;//n为邻接矩阵顶点总数 ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); G->arcnum=g->arcnum; G->vexnum=g->vexnum; for(i=0;i for(i=0;i if(g->adj[i][j]!=INFINITY)//邻接矩阵的当前元素不为 { p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*p G->AdjList[j].data=g->vexs[j];//顶点数据元素赋值 p->adjvex=g->vexs[j];//给邻接点数组中的每一个头结点赋值 p->info=g->adj[i][j];//给邻接链表赋上权值 p->nextarc=G->AdjList[i].firstarc;//将*p链到链表后 G->AdjList[i].firstarc=p;//将i转变为邻接表数组的头结点 } } returnG; } voidoutput_graphic_c(MGraph*g,ALGraph*G) { inti; ArcNode*p;//ArcNode弧的结点结构类型 for(i=0;i printf(\"%c\输出邻接表数组的头结点元素 p=G->AdjList[i].firstarc;//邻接表的头指针 while(p!=NULL) { printf(\"%s\整个一条单链表输出 printf(\"(%c,%d)\p=p->nextarc; } printf(\"\\n\\n\"); } } voidoutput_Find_ALGraph(ALGraph*G,charvp) {/*相邻景点查询并输出*/ intj; ArcNode*p; //printf(\"请输入你要查询的景点:\\n\"); //scanf(\"%d\//scanf(\"%c\j=LocateVexx(G,vp); p=G->AdjList[j].firstarc;//邻接表的头指针 while(p) { printf(\"景点%c到景点%c的距离是%d(该两个景点之间有直接的道路相 通)\\n\p=p->nextarc;//指向下一个结点指针 } printf(\"\\n\\n\"); } voidDijkstra_One(ALGraph*G,MGraph*g,charv0,intdistance[],intpre[]) {//S[]为已求得最短路径的终点集 //带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre //数组pre[n]保存从Vs到其它顶点的最短路径。若pre[i]=k，表示从Vs到Vi的最短路径中，Vi的前一个顶点是Vk， intw,m; intS[30],i,j,k,p,min; m=LocateVexx(G,v0); //printf(\"你所要开始查询的景点是:%c\\n\for(i=0;i distance[i]=g->adj[m][i]; S[i]=0; if(distance[i] S[m]=1;//顶点v0已加入到集合S中设置s={v0} for(i=0;i min=INFINITY; for(j=0;j if(!S[j]&&distance[j] /*求出当前最小的distance[j]值*/ } } S[k]=1;//将找到的顶点j加入到集合S中 for(w=0;w distance[w]=distance[k]+g->adj[k][w]; pre[w]=k;//修改distance和pre数组的值 } } printf(\"查询结果:\\n\");//找到最短路径 for(j=0;j printf(\"从景点%c到景点%c\p=pre[j]; printf(\"的最短距离是:%d\printf(\"途中经过的景点有:\"); while(p!=-1) { printf(\"%c\p=pre[p]; } printf(\"\\n\"); } elseif(j!=m) printf(\"\\n%c到%c:nopath\} voidDijkstra_Two(ALGraph*G,MGraph*g,charv0,chard,intdistance[],intpre[]) { //带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre intw,m,n; intS[30],i,j,k,p,min; //chard; m=LocateVexx(G,v0); //printf(\"你所要开始查询的开始景点是:%c\\n\\n\for(i=0;i distance[i]=g->adj[m][i]; S[i]=0; if(distance[i] min=INFINITY; for(j=0;j if(!S[j]&&distance[j] }/*求出当前最小的distance[j]值*/ S[k]=1;//将找到的顶点加入到集合S中 for(w=0;w distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; }//修改distance和pre数组的值 } //printf(\"输入你要查询的另外一个景点(下标值):\"); //scanf(\"%c\n=LocateVexx(G,d); //printf(\"你要查询的另外一个景点是:%c\\n\printf(\"\\n查询结果:\\n\");//输出结果 if(pre[n]!=-1) { printf(\"从景点%c到景点%c\ p=pre[n]; printf(\"的最短距离是:%d\printf(\"途中经过的景点有:\"); while(p!=-1) { printf(\"%c\p=pre[p]; } printf(\"\\n\"); } } voiddfs_path(ALGraph*g,intsrc,intcur,intvis[],GPath*cur_path,GPath*min_path) { if(vis[src]) { if(cur_path->count==g->vexnum) { if(cur_path->value memcpy(min_path,cur_path,sizeof(GPath));/*由cur_path所指内存区域复制sizeof(GPath)个字节到min_path所指内存区域*/ return; } } return; } ArcNode*node=g->AdjList[cur].firstarc; for(;node!=NULL;node=node->nextarc)/*起 node=g->AdjList[cur].firstarc*/ { charadj=node->adjvex; intindex=LocateVexx(g,adj); if(vis[index]==0) { cur_path->vertex[cur_path->count++]=index; cur_path->value+=node->info; vis[index]=1; dfs_path(g,src,index,vis,cur_path,min_path); cur_path->count--; cur_path->value-=node->info; vis[index]=0; } } 始 条 件 为 } voidbest_path(ALGraph*g,intsrc) { intvis[MAXVEX]; memset(vis,0,sizeof(vis)); GPathcur_path,min_path; memset(&cur_path,0,sizeof(GPath));/*将cur_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向cur_path的指针。*/ memset(&min_path,0,sizeof(GPath));/*将min_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向min_path的指针。*/ min_=INFINITY; dfs_path(g,src,src,vis,&cur_path,&min_path); if(min_!=INFINITY) { inti=0; printf(\"\\n最佳旅游路线景点下标值是:\\n\"); for(i=0;i printf(\"\\n\"); printf(\"\\n最佳旅游路线景点是:\\n\"); for(i=0;i printf(\"\\n\"); }else { printf(\"建立的图中没有最佳路径\\n\"); } } voidmain() {intm; intn,opse; charvp,v0,d,src; intdistance[MAXVEX],pre[2*MAXVEX]; ALGraph*G; MGraph*M; do {printf(\"\\n\\n请选择对图的操作要求:\\n\\n\"); for(n=0;n<=5;n++) printf(\"*\"); printf(\"\\n*\"); printf(\"1----建立图的邻接矩阵\"); printf(\"2----图的邻接矩阵的输出\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"3----图的邻接链表的输出\"); printf(\"4----相邻景点查询(下标值)\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"5----从某点出发到另外所有点最短简单路径及距离(下标值)\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"6----两个景点之间的最短距离(下标值)\"); printf(\"*\\n\"); printf(\"\\n*\"); printf(\"7----最佳路径\"); printf(\"8----退出\"); printf(\"*\\n\"); for(n=0;n<=5;n++) printf(\"*\"); printf(\"\\n\\n\"); do {scanf(\"%d\}while(opse<1||opse>8); switch(opse) { case1: {M=(MGraph*)malloc(sizeof(MGraph)); M=create_graph(); printf(\"\\n\\n\"); break; } case2: {printf(\"\\n您所建立的图是：\\n\"); output_graphic(M); break; } case3: {printf(\"图G的邻接矩阵转换成邻接表:\\n\"); G=MGraphToALGraph(M,G); output_graphic_c(M,G); break; } case4: { printf(\"\\n请输入你要查询的景点：\\n\"); scanf(\"%c\ output_Find_ALGraph(G,vp); break; } case5: { printf(\"\\n输入一个顶点是：\\n\"); scanf(\"%c\ Dijkstra_One(G,M,v0,distance,pre); break; } case6: { printf(\"你所要开始查询的开始景点是:\\n\\n\"); scanf(\"%c\ printf(\"你要查询的另外一个景点是:\\n\"); scanf(\"%c\ Dijkstra_Two(G,M,v0,d,distance,pre); break; } case7: { printf(\"输入你要查询的开始景点:\"); scanf(\"%c\m=LocateVexx(G,v0); best_path(G,m); break; } } }while(opse!=8); } ⒍ 问题与总结 问题： 1、第一次答辩的时候，老师要求景点名称在后面也要输入字符型，回来后，想了一下，用了一个简单的办法，即调用LocateVexx函数返回我输入景点所对应的下标值。这样就避免了只能输入下标值带来的不便了； 2、没有完全符合最后一题的意思完成该题，最后一小题题目要求是可以重复经过某些点，但是我的程序是每个点只经过一次的最短 回路（即所建的图需是哈密顿图才有回路，否则会输出没有最短路径）；为了解决这个问题，我在网上也看了很多的资料，比如：TSP问题（旅行商问题/货郎担问题）、蚁群算法、、模拟退火算法、KM算法、中国邮递员算法等，其中发现经典的旅行商问题（货郎担问题）并不符合题目最后一题的要求，下面是在网上截图的资料： 为了解决这个难题，虽然在网上找了很多的资料，努力了三天，但是还是没有能力解决这个问题。 总结：将邻接矩阵转换为邻接链表走了很多弯路、花了很长的时间；还有就是引用一些书上的函数时，要正确用函数对结构体成员调用，不能照搬过来，得看一下结构上的区别。 感谢阅读 因篇幅问题不能全部显示，请点此查看更多更全内容