《校园导游图C++》由会员分享，可在线阅读，更多相关《校园导游图C++（14页珍藏版）》请在金锄头文库上搜索。
1、题目13 图（校园导游图）*1、问题描述制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边）2、要求（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。3、实现提示（1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。（2）第二问可采用深度优先搜索，如果有多种路径可
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 Tou
3、ristmapspublic: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=
4、0;cout 编序 名称 简介：gh.vnum;for(i=0;igh.vi.serialgh.vi.namegh.vi.intro;cout景点编号count: gh.vi.serial gh.vi.name gh.vi.introendl;count+;infile.close();coutgh.vnum;for(int i=0;igh.vi.serialgh.vi.namegh.vi.intro;if(strcmp(gh.vi.name,select)=0|strcmp(gh.vi.serial,select)=0)obj=i;exist=1;if(!exist)cout未找到要查询的相
5、关信息！endl;elsecout您要查询的信息如下：endl;cout景点编序：gh.vobj.serialendl;cout景点名称：gh.vobj.nameendl;cout景点信息：gh.vobj.introendl;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;igh.vi.serialgh.v
6、i.namegh.vi.intro;ofstream outfile2(graph.txt,ios:out);coutcount;gh.vnum=gh.vnum+count;outfile2gh.vnumendl;for(i=0;if;i+)outfile2gh.vi.serial gh.vi.name gh.vi.introendl;outfile2.close();infile.close();ofstream outfile(graph.txt,ios:app);cout请依次输入景点编序, 名称, 简介：endl;for( i=f;igh.vnum ;i+)cout第i+1gh.vi.
7、serialgh.vi.namegh.vi.intro;outfilegh.vi.serial gh.vi.name gh.vi.introendl;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;
8、cout与景点相关信息的输入endl;for(i=f;igh.vnum;i+)cout请输入与gh.vi.name景点相邻的所有权值(没有路径时输入10000)endl;for(j=0;jgh.vnum & j!=i;j+)cout请输入gh.vi.name与gh.vj.name景点权值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
9、,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
10、.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逆序输出所经过的景点的路径
