1、数据结构实验图实验7：图的应用一、实验目的图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。二、问题描述给出一张某公园的导游图，游客通过终端询问可知：a) 从某一景点到另一个景点的最短路径。b) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。三、实验要求1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；1、 为游客提供任意两个景点之间的一条最短的简单路径。2、 为游客选择最佳游览路径。 四、实验环境PC微机
2、DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、设计公园平面图，图中顶点表示公园的各个景点，存放名称、代号、简介等信息；边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；4、选择适当语言实现算法；3、 调试程序。 六、测试数据 可根据实际情况指定。 测试数据见南昌大学平面示意图。七、实验报告要求1、 问题描述； 该程序包扩以下内容： （1）设计学校
3、的校园平面图，所含景点为9个。（2）以图中顶点表示校内各景点，存放景点名称、代号、间介等信息；以边表示路径，存放路径长度等相关信息。（3）为来访客人提供图中任意景点相关信息的查询。（4）提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。（5）提供途中任意景点问路查询，即求任意两个景点间的所有路径。（6）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。设计思路：对系统功能抽象，分析问题描述。首先，平面图用输出模拟；存储景点信息采用结构体；对各景点用字母代替，字母组成图，通过对图的操作，狄克斯特拉算法求出指定最短路径及一点到其它所有点的最短路径，递归进行
4、图的遍历求两点所有路径。由此可实现以上所有功能。2、 图的建立图的建立：这是一个无向带权图，实际上无向带权图与有向带权图相似，采用邻接矩阵存储比较方便。邻接矩阵的结点结构体如下：其赋值如下：3、 图的最短路径算法算法思想：设置两个结点集合S和T，集合S中存放已找到的最短路径的结点，集合T中存放当前还没找到的最短路径的结点。初始状态时，集合S中只包含源点，没为v0，然后不断的从集合T中选择到源点v0的路径长度最短的结点u加入到集合S中，集合S中每加入一新的结点u，都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各点的新的当前最短路径长度值为原来的当前最短路径长度值，与结点u的最短
5、路径长度值加上结点u到该结点的路径长度值（即为从源点结点u到达该结点的路径长度）中的较小者。此过程不断重复，直到集合T中的对号点全部加到集合S中为止。算法实现如下： void Dijkstra(MGraph g,int v, int to) n 简介：endlendl;void browse()览学校景点 2.查找单个景点信息 endl; cout 3.学校地图平面示意图 4.路线推荐 endl; cout 5.景点最短线路 6.两景点所有路径 endl; cout 7.退出系统 endl; cout endl;void FunMenue2()学校大门 B. 和平女神像endl; cout C
6、. 体 育 馆 D. 游 泳 馆 endl; cout E. 商 业 街 F. 教 学 主 楼endl; cout G. 正 气 广 场 H. 图 书 馆endl; cout I. 天 健 园 key; switch(key) case A:return A;break; case B:return B;break; case C:return C;break; case D:return D;break; case E:return E;break; case F:return F;break; case G:return G;break; case H:return H;break; ca
7、se I:return I;break; default:cout您的输入有误！请选择AI！n;system(pause);system(cls);FunMenue2();C_IN2(); int Sprint(char item)/对字母表示的景点输出 switch(item) case A:cout;break; case B:cout;break; case C:cout;break; case D:cout;break; case E:cout;break; case F:cout;break; case G:cout;break; case H:cout;break; case I:
8、cout;break; default:cout无此景点n;return 1;break; return 0;#endif/构造图 及图的相关操作，由狄克斯拉算法改成。#include #define MAXV 100 #define INF 32767 typedef int InfoType; /邻接矩阵存储方法 typedef struct int edgesMAXVMAXV; int n; MGraph; /狄克斯特拉算法 void Ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; Ppath(path,k,v);
9、Sprint(k+A); coutchar(k+A); void Dispath(int dist,int path,int s,int n,int v,int i) /对最短路径输出 if(si=1) cout ; Sprint(v+A); coutchar(v+A)到; Sprint(i+A); coutchar(i+A)n 最短路径：disti米 n 途经： ; Sprint(v+A); coutchar(v+A); Ppath(path,i,v); Sprint(i+A); coutchar(i+A)endl; else cout从char(v+A)到char(i+A)不存在的路径en
10、dl; cout; void Dijkstra(MGraph g,int v, int to) /Dijkstra g图中v为起点求出到所有点的最短路径 int distMAXV,pathMAXV; /dist存路径 path存顶点 int sMAXV; /标记 int mindis,i,j,u; for(i=0;i;i+) disti=vi; si=0; ifviINF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;i;i+) mindis=INF; for(j=0;j;j+) if(sj=0&distjmindis) u=j; mindis=
11、distj; su=1; for(j=0;j;j+) if(sj=0) ifujINF&distu+ujdistj) distj=distu+uj; pathj=u; Dispath(dist,path,s,v,to); void Dijkstra(MGraph g,int v)/重载，当只有一点求最短路径时，用到 int to; for(to=0;to;to+) if(to=v)continue; Dijkstra(g,v,to); /int path10;int pathF10=0;int BPsize=0;int EofV(MGraph g,int start) int con=0; f
12、or(int j=0;j;j+) ifstartj!=0&startjINF) con+; return con;int Nest(MGraph g,int start,int i) int con=0; for(int j=0;j;j+) ifstartj!=0&startjINF) con+; if(con=i) return j; return 0;void Print(MGraph g) /打印找到路径 int TVal=0; for(int j=0;jBPsize-1;j+) TVal=TVal+pathjpathj+1; Sprint(pathj+A); cout; Sprint(
13、pathj+A); coutn总 长：TVal 米endl;void FindAllWay(MGraph g,int start,int end,int n) /寻找所有路径 int i; if(start=end) pathn=start; BPsize=n+1; Print(g); return ; int num=EofV(g,start); pathn=start; for(i=1;i=num;i+) if(pathFNest(g,start,i)!=1) pathFstart=1; FindAllWay(g,Nest(g,start,i),end,n+1); pathFstart=0
14、; /Shortest函数 int Shortest(int choice) /最短路径函数 char from,to; int i,j,n; MGraph g; n=9;/图信息 for(i=0;in;i+) for(j=0;jn;j+) if(i!=j) ij=32767; else ij=0; 01=10=100; 02=20=500; 06=60=200; 07=70=350; 23=32=150; 35=53=250; 45=54=200; 48=84=800; 57=75=600; 67=76=400; 78=87=300; =n; if(choice=5) cout请输入起点和终
15、点：fromto; cout+竭诚为您提供最短路径+; i=from-A;j=to-A; Dijkstra(g,i,j); coutendl; if(choice=4) cout请输入起点：from; system(cls); cout+我为您提供这里到学校其它景点最好选择+; cout 您选择了; if(Sprint(from)=1)return 0; cout为起点n; i=from-A; Dijkstra(g,i); coutendl; if(choice=6) cout请输入起点和终点：fromto; int f,t; f=from-A; t=to-A; FindAllWay(g,f,
16、t,0); return 0; #include #include void exc();void C_IN(void)/对主选单操作 char key; cinkey; switch(key) case 1:browse();break; case 2:FunMenue2();S_print(C_IN2();system(pause);system(cls);break; case 3:Gprint();break; case 4:FunMenue2();Shortest(4);system(pause);system(cls);break; case 5:FunMenue2();Short
17、est(5);system(pause);system(cls);break; case 6:FunMenue2();Shortest(6);system(pause);system(cls);break; case 7:coutnn 欢迎您的到来，谢谢您的使用！n; cout 学校主页：; exc(); default:cout您的输入有误！请选择14！n;system(pause);system(cls);FunMenue();C_IN(); void exc() coutkey; while(key!=Y&key!=N) cinkey; if(key=Y) exit(1); if(key=N) system(cls); FunMenue();C_IN();int main()/主函数 while(1) FunMenue(); C_IN(); return 0;
