南昌航空大学数据结构与算法实验六.doc

南昌航空大学实验报告课程名称： 数据结构与算法 实验名称： 实验六 图的遍历 班 级： XXX 学生姓名： XXX 学号： XXXXX 指导教师评定： XXX 签 名: XXX 一、实验目的图结构有着广泛的应用。二、实验内容本实验主要涉及两个方面的内容：一个是有关图的最短路径问题，用一个交通查询系统例子来验证迪杰斯特拉算法和费洛伊德算法；而另一个则工程项目实施过程中的关键路径问题。三、程序分析设计一个交通查询系统，能让游客查询从任一城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。对于不同查询要求，可输入城市间的路程或所需时间或所需费用。本程序共分三个部分：（1）建立交通网络图的存储结构；（2）单源最短路径；（3）实现两个城市顶点之间的最短路径。四、程序源代码该实例程序的源代码如下：（1）建立有向图的存储结构/文件名CreateMGraph.cVoid CreateMGraph(MGraph * G，int n，int e)/采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jvexsij=Maxint;/初始化邻接矩阵printf(输入%d条边的i、j及w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕n);/文件dijkstra.cvoid Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxint)P2v=v1;elsep2v=0;D2v1=0;Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw& D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;P2w=v;printf(路径长度路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=P2i;while(v!=0)printf(-%d,v);v=P2v;printf(n);/文件floyd.cvoid Floyd(MGraph *G,int n)int i,j,k,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+Dkj%d,k);k=Pkw;printf(-%d,w);printf(路径长度:%dn,Dvw);elseif(xz=1)printf(求单源路径，输入源点v:);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径,再见!n);五、实验结果输入图中顶点个数和边数n，e：7，10(表示输入7个顶点和10条边)输入10条边的i、j及w1，7，92，1，202，3，102，4，303，5，55，4，125，7，156，5，86，7，107，3，18有向图的存储结构建立完毕*求城市之间的最短路径*=1求一个城市到所有城市的最短路径2求任意的两个城市之间的最短路径=请选择： 1、或 2、选择 0、退出：1求单源路径，输入源点v:1（表示求从顶点1到其他所有顶点的最短路径）路径长度 路径01 /说明顶点1到1路径长度为0327672 /说明顶点1到2无路径，32767表示27 3-7-1 /说明顶点1到3路径长度为27，路径为1，7，344 4-5-3-7-132 5-3-7-132767697-1*求城市之间的最短路径*=1求一个城市到所有城市的最短路径2求任意的两个城市之