校园导游图C++.doc

题目13 图（校园导游图）*1、问题描述制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边）2、要求（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。3、实现提示（1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。 #include#include#includeusing namespace std;#define MAX_INT 10000#define MAX 20int visitedMAX=0;int p1MAX;/前驱顶点int cost;int pathMAXMAX,shortestMAXMAX;/用path记录从i到j的最短路径上点j的前驱景点的序号struct vexchar name20;char serial30;char intro200;struct graphvex v15;int arc1515;int vnum;class Touristmapspublic:void display(graph); /查看所有景点信息void scanf(graph,char*); /查看某个景点信息void add(graph &); /增加景点void start(graph); /初始化景点信息int shortestdistance();/用佛洛依德算法求最短路径void floyed(); /用佛洛依德算法求void print(int,int);/打印两个景点间的路径及最短距离void DFS(int,int);/深度遍历;void Touristmaps:display(graph gh)int i;int count=0;cout 编序 名称 简介：gh.vnum;for(i=0;ro;cout景点编号count: gh.vi.serial roendl;count+;infile.close();coutgh.vnum;for(int i=0;ro;if(strcmp(,select)=0|strcmp(gh.vi.serial,select)=0)obj=i;exist=1;if(!exist)cout未找到要查询的相关信息！endl;elsecout您要查询的信息如下：endl;cout景点编序：gh.vobj.serialendl;cout景点名称：endl;cout景点信息：roendl;infile.close();system(pause);system(cls);void Touristmaps:add(graph &gh)int i,j,count,f;ifstream infile(graph.txt,ios:in);if(!infile)cout文件打开失败！gh.vnum;f=gh.vnum;for(i=0;ro;ofstream outfile2(graph.txt,ios:out);coutcount;gh.vnum=gh.vnum+count;outfile2gh.vnumendl;for(i=0;if;i+)outfile2gh.vi.serial roendl;outfile2.close();infile.close();ofstream outfile(graph.txt,ios:app);cout请依次输入景点编序, 名称, 简介：endl;for( i=f;igh.vnum ;i+)cout第i+1ro;outfilegh.vi.serial roendl;outfile.close();ifstream infile1(linjiejuzhen.txt,ios:in);for(i=0;if;i+)for(j=0;jgh.arcij;infile1.close();ofstream outfile1(linjiejuzhen.txt,ios:out);for(i=f;igh.vnum;+i) for(j=0;jgh.vnum;+j)gh.arcij=MAX_INT;gh.arcji=MAX_INT;cout与景点相关信息的输入endl;for(i=f;igh.vnum;i+)cout请输入与景点相邻的所有权值(没有路径时输入10000)endl;for(j=0;jgh.vnum & j!=i;j+)cout请输入与景点权值gh.arcij;gh.arcji=gh.arcij;for(i=0;igh.vnum;i+)outfileendl;for(j=0;jgh.vnum;j+)outfile1gh.arcijendl;outfile1.close();cout添加景点信息成功g.vnum;infile.close();int i,j;coutg.vnum-1)数字编号ij;if(i=g.vnum|i=g.vnum|j0)cout输入信息错误！nn;coutg.vnum-1)数字编号ij;elsefloyed();print(i,j);system(pause);system(cls);return 1;void Touristmaps:floyed() int i,j,k;graph g;ifstream infile1(graph.txt,ios:in);infile1g.vnum;infile1.close();ifstream infile(linjiejuzhen.txt,ios:in);for(i=0;ig.vnum;i+)for(j=0;jg.arcij;infile.close();for(i=0;ig.vnum;i+)for(j=0;jg.vnum;j+)shortestij=g.arcij;pathij=-1;for(k=0;kg.vnum;k+)for(i=0;ig.vnum;i+)for(j=0;j(shortestik+shortestkj)shortestij=shortestik+shortestkj;pathij=k;/用path记录从i到j的最短路径上点j的前驱景点的序号pathji=k;void Touristmaps:print(int i,int j) int a,b;a=i;b=j;cout要查询的两景点间最短路径是:nn;cout逆序输出所经过的景点的路径:;if(shortestij!=MAX_INT)if(ij)cout=0)cout-pathij;/把i到j的路径上所有经过的景点按逆序打印出来if(ij)j=pathij;elsei=pathji;cout-aendlendl;coutab最短距离是:shortestabendl;elsecout=0) coutpathij;/把i到j的路径上所有经过的景点按顺序打印出来if(ij)j=pathij;elsei=pathji;coutbendl;coutab的最短距离是:shortestabendlendl;elsecoutg.vnum;for(i=0;ro;infile1.close();ifstream infile(linjiejuzhen.txt,ios:in);for(i=0;ig.vnum;i+)for(j=0;jg.arcij;infile.close();p1p10+ = x;/x加入路径if(x=b)/找到一条路径则输出+n;cout第n条途径：endl;for(i=1;ip10;i+);cout 路径长度:cost;coutendl;return;for(j=0;jg.vnum;j+)if(g.arcxj!=10000&! visitedx) /x到j有路，并且x到j没走过cost+=g.arcxj;/记录总的路径visitedx = 1;/标记已走DFS(j,b);p10-;/去掉jcost-=g.arcxj;/恢复visitedx = 0;/恢复void Touristmaps:start(graph g)char x;coutx;if(x=y|x=Y)ofstream outfile(graph.txt,ios:out);g.vnum =0;outfileg.vnum;outfile.close();ofstream outfile1(linjiejuzhen.txt,ios:out);outfile.close();cout初始化成功！endl;elsecout你没有初始化!endl;system(pause);system(cls);void main()graph GH;int x,y;char select10;Touristmaps map;while(1)cout endl;cout 欢迎使用景德镇陶瓷学院校园导游系统 endl;cout endl;cout endl;cout 1.查看所有信息 2.查某景点信息 endl;cout endl;cout 3.添加景点信息 4.两点间所有路径 endl;cout endl;cout 5.两点间最短路径 6.初始化景点信息 endl;cout endl;cout 0.退出导游系统 endl;cout * endl;cout 学校景点概括 endl;coutGH.vnum;for(int i=0;iGH.vi.serialGH.GH.ro;coutsetw(21)iGH.endl;infile.close();cout *endl;coutchoose;switch(choose)case 1:map.display(GH);break;case 2:coutselect;map.scanf(GH,select);break;case 3:map.add(GH);break;case 4:ifstream infile(graph.txt,ios:in);infileGH.vnum;infile.close();coutGH.vnum-1)数字编号xy;if(x=GH.vnum|x=GH.vnum|y0) cout