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

《南昌航空大学数据结构与算法实验六.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌航空大学实验报告课程名称：数据结构与算法实验名称：实验六图的遍历班级：XXX学生姓名：XXX学号：XXXXX指导教师评定：XXX签名:XXX一、实验目的图结构有着广泛的应用。二、实验内容本实验主要涉及两个方面的内容：一个是有关图的最短路径问题，用一个交通查询系统例子来验证迪杰斯特拉算法和费洛伊德算法；而另一个则工程项目实施过程中的关键路径问题。三、程序分析设计一个交通查询系统，能让游客查询从任一城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。对于不同查询要求，可输入城市间的路程或所需时间或所需费用。

2、本程序共分三个部分：（1）建立交通网络图的存储结构；（2）单源最短路径；（3）实现两个城市顶点之间的最短路径。四、程序源代码该实例程序的源代码如下：　　（1）建立有向图的存储结构　　//文件名CreateMGraph.c　　VoidCreateMGraph(MGraph*G，intn，inte)　　{//采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j

3、++)G->vexs[i][j]=Maxint;//初始化邻接矩阵printf("输入%d条边的i、j及w:",e);for(k=1;k<=e;k++){scanf("%d,%d,%d,",&i,&j,&w);G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕");　　　　}　　//文件dijkstra.c　　voidDijkstra(MGraph*G,intv1,intn)　　{intD2[MVNum],P2[MVNum];intv,i,w,min;enumbooleanS[MVNum

4、];for(v=1;v<=nv++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]arcs[v][w]

5、2[v]+G->arcs[v][w];P2[w]=v;}}printf("路径长度路径");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=P2[i];while(v!=0){printf("<-%d",v);v=P2[v];}printf("");　　}　　　}　　　//文件floyd.c　　　voidFloyd(MGraph*G,intn)　　{inti,j,k,w;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(G

6、->arcs[i][j]!=Maxint)P[i][j]=j;elseP[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]

7、{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];#include"CreateMGraph.c"#include"dijkstra.c"#include"floyd.c"voidmain(){MGrap

8、h*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);w,hile(xz!=0){printf("********求城市之间的最短