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

-1-计算机系数据结构实验报告（6）实验目的：图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。问题描述：给出一张某公园的导游图，游客通过终端询问可知：a)从某一景点到另一个景点的最短路径。b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。实验要求：文法是一个四元1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；3、为游客提供任意两个景点之间的一条最短的简单路径。4、为游客选择最佳游览路径。算法分析：1、设计公园平面图，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；实验内容和过程：源程序：#includeiostreamusingnamespacestd;#includestdio.h#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20#defineVRTypeint#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_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;-2-}MGraph;voidDFS(MGraphG,intv);voidVisitFunc(MGraphG,intv);intFirstAdjVex(MGraphG,intv);intNextAdjVex(MGraphG,intv,intw);VertexTypeOutVex(MGraphG,intm);typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_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输入景点个数，道路条数:;cinG.vexnumG.arcnum;cout输入各个景点:;for(i=0;iG.vexnum;++i)cinG.vexs[i];for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}cout输入每条道路依附的景点和道路长度:endl;for(k=0;kG.arcnum;++k){cinv1v2w;i=LocateVex(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;vG.vexnum;++v)visited[v]=false;-3-for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);}voidDFS(MGraphG,intv){intw;visited[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;iG.vexnum;i++)if(G.arcs[v][i].adj!=INFINITY)returni;if(i==(G.vexnum-1))return-1;return-1;}intNextAdjVex(MGraphG,intv,intw){inti;for(i=w+1;iG.vexnum;i++)//+1if(G.arcs[v][i].adj!=INFINITY)returni;if(i==(G.vexnum-1))return-1;return-1;}voidVisitFunc(MGraphG,intv){coutG.vexs[v];}voidShortestpath_DIJ(MGraphG,intv0,PathMatrix*p,ShortPathTable*D){intv,w,i,j,min;intfinal[MAX_VERTEX_NUM];for(v=0;vG.vexnum;v++){final[v]=FALSE;(*D)[v]=G.arcs[v0][v].adj;for(w=0;wG.vexnum;w++){(*p)[v][w]=FALSE;}if((*D)[v]INFINITY){(*p)[v][v0]=TRUE;(*p)[v][v]=TRUE;}}(*D)[v0]=0;-4-final[v0]=TRUE;for(i=1;iG.vexnum;i++){min=INFINITY;for(w=0;wG.vexnum;w++){if(!final[w]){if((*D)[w]min){v=w;min=(*D)[w];}}}final[v]=TRUE;for(w=0;wG.vexnum;w++){if(!final[w]&&minINFINITY&&G.arcs[v][w].adjINFINITY&&(min+G.arcs[v][w].adj(*D)[w])){(*D)[w]=min+G.arcs[v][w].adj;for(j=0;jG.vexnum;j++){(*p)[w][j]=(*p)[v][j];}(*p)[w][w]=TRUE;coutOutVex(G,v);}}}}intmain(){PathMatrixp;ShortPathTabled;charn1,n2;intm,i,j;MGraphG;CreateUDN(G);cout1，最佳游览路径\n2,任意两景点最短路径\n3，退出endl;cinm;if(m==1)DFSTraverse(G);elseif(m==2){cout输入起点和终点：;cinn1n2;-5-cout两个景点之间最短的简单路径为：;coutn1;Shortestpath_DIJ(G,LocateVex(G,n1),&p,&d);coutn2;cout最短路径总距离为:d[LocateVex(G,n2)]endl;}elseif(m==3)exit(0);elsecoutERRORendl;}实验结果：测试图：-6-总结和感想：难度大，C有待加强，理论知识不够充分，之后还需测试改进。