数据结构实验(6)图的应用.doc

《数据结构实验(6)图的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.计算机系数据结构实验报告（6）实验目的：图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。问题描述：给出一张某公园的导游图，游客通过终端询问可知：a)从某一景点到另一个景点的最短路径。b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。实验要求：文法是一个四元1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；3、为游客

2、提供任意两个景点之间的一条最短的简单路径。4、为游客选择最佳游览路径。算法分析：1、设计公园平面图，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；实验内容和过程：源程序：#includeusingnamespacestd;#include#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20#defi

3、neVRTypeint#defineInfoTypeint#defineVertexTypechar#defineMAX10#defineFALSE0#defineTRUE1typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VER

4、TEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;范文..}MGraph;voidDFS(MGraphG,intv);voidVisitFunc(MGraphG,intv);intFirstAdjVex(MGraphG,intv);intNextAdjVex(MGraphG,intv,intw);VertexTypeOutVex(MGraphG,intm);typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTE

5、X_NUM];typedefintShortPathTable[MAX_VERTEX_NUM];intLocateVex(MGraphG,VertexTypev){inti=0;for(i=0;G.vexs[i]!=v;++i);returni;}VertexTypeOutVex(MGraphG,intm){returnG.vexs[m];}boolCreateUDN(MGraph&G){inti,j,k;charv1,v2;intw;G.kind=UDN;cout<<"输入景点个数，道路条数:";cin

6、>>G.vexnum>>G.arcnum;cout<<"输入各个景点:";for(i=0;i>G.vexs[i];for(i=0;i>v1>>v2>>w;i=LocateVex(

7、G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i]=G.arcs[i][j];}returntrue;}boolvisited[MAX];voidDFSTraverse(MGraphG){intv;for(v=0;v

8、[v]=true;VisitFunc(G,v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}intFirstAdjVex(MGraphG,intv){inti;for(i=0;i