实验八图的应用

《实验八图的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验八图的应用(设计性实验)一、实验目的通过最短路径算法的实现，掌握图的存储结构特点和有关图的基本操作。二、实验准备1.图的定义和基本术语；2.图的四种存储结构（数组表示法、邻接表、十字链表和邻接多重表）；3.图的两种遍历策略（深度优先搜索和广度优先搜索），并应该注意图的遍历和树的遍历算法之间的区别；4.图的连通性、连通分量和最小生成树的概念和实现方法；5.拓扑排序和关键路径、两类求最短路径问题的解法。6.部分相关代码：⑴图的结构定义（这里使用数组表示法）#defineinfinity10000#definem

2、ax_vertex_num20typedefintvrtype;typedefenum{dg,dn,udg,udn}graphkind;typedefstructarccell{vrtypeadj;infotype*info;}adjmatrix[max_vertex_num][max_vertex_num];typedefstruct{vertextypevexs[max_vertex_num];adjmatrixarcs;intvexnum,arcnum;graphkindkind;}mgraph;⑵迪杰斯

3、特拉算法voidshortestpath_dij(mgraphg,intv0,pathmatrixp,shortpathtabled){for(v=0;v

4、in=infinity;lfor(w=0;w

5、matrixd){for(v=0;v

6、]#defineN20#defineTRUE1#defineFALSE0intvisited[N];typedefstruct/*队列的定义*/{intdata[N];intfront,rear;}queue;typedefstruct/*图的邻接矩阵*/

7、{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/voiddfs(inti,graph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(graph*g);/*深度优先搜索整个图*/voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/voidtbfs(graph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识

8、数组*/voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/{inti,j;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;/*顶点数目*/for(i=0;