图最少连通路径集课程设计

1、沈阳航空航天大学课 程 设 计 报 告课程设计题目：图的最少连通路径集院（系）：计算机学院专业：计算机科学与技术班级：*学号：*姓名：*指导教师：许莉沈阳航空航天大学课程设计报告目 录1 题目的要求和内容11.1图的最少连通路径集11.2课设内容11.3课设要求12系统功能结构模块图22.1功能模块图22.2生成树模块的具体演示操作22.3模块功能说明43 测试/运行结果8参考文献10附 录1111 题目的要求和内容1.1图的最少连通路径集在无向图G中，如果从顶点V到顶点V1有路径，则称V和V1是连通的；如果对于图中任意两点V1，V2都是连通的，则称G是连通图。如果给定一个带权值的图（又叫网）

2、且是一个连通图则该图一定存在最小连通路径集即该图的最小生成树。1.2课设内容给定一个无向图，代表一个特定的网络连接关系，现根据这个图求出一组路径，路径中包含节点仅一次，并且途中所有节点至少属于其中一条路径，要求求出的路径集合中包含的路径数量最少。1.3课设要求1.利用所学知识，设计相应的数据结构2.熟练运用开发环境3.完成软件的设计与编程4.熟练掌握基本的调试方法5.提交符合课程设计规范的报告2 系统功能结构模块图2.1功能模块图本程序由以下几个模块构成生成树模块最小生成树建图模块顶点定位模块寻找最小权值模块图2.1 系统模块2.2生成树模块的具体演示操作1.普利姆算法实现过程演示(寻找最小权

3、值的过程)：9V5V311V4V1 图2.2V5V21V3V5V3V4V2V112114935117图2.2V1V41第一步：第二步：第三步：图2.2生成树模块具体实现的演示操作 V252.3模块功能说明1.建图模块通过输入的节点数和弧数来控制输入的节点数和弧数，并通过数组一个一维数组储存顶点和一个二维数组储存弧信息，边信息的储存是一个领接矩阵，领接矩阵的数为无穷大或者为相应的权值，相应流程图如下：输入顶点个数：vexnum输入弧数：arcnumFor(i=0,ivexnum,i+)输入顶点数,(*G).vexsi)for(i=0;i(*G).vexnum;+i) for(j=0;j(*G).

4、vexnum;+j)领接矩阵初始化: (*G).arcsij.adj=INFINITY输入节点va,vb及两顶点之间的权值wi=LocateVex(*G,va)j=LocateVex(*G,vb)权值的储存及反向弧:(*G).arcsij.adj=(*G).arcsji.adj=w找出va vb在一维数组中的位置图2.3 建图模块结束开始2.生成树模块此模块采用普利姆算法实现，此算法实现的建立在顶点定位模块和寻找最小权值模块的基础上，首先定位首个顶点（该顶点是程序默认的一维数组的第一个元素），通过定位模块找出顶点在一维数组中的位置，再通过辅助数组与寻找最小权值模块进行比较后将该顶点在领接矩阵中

5、的值赋给辅助数组，最后通过辅助数组用同样的方式找出图中剩余顶点相连的弧的最小权值，然后打印出所有的顶点的最小边即最小生成树实现流程图如下：开始k=LocateVex(G,u)辅助数组初始化for(j=0;jG.vexnum;+j)if(j!=k)复制顶点及权值到辅助数组：strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgej.lowcost=G.arcskj.adj;求出图中的下个顶点For(i=1,iG.vexnum,+i)k=minimum(closedge,G)输出生成树的边：printf(%s-%s)n,c

6、losedgek.adjvex,G.vexsk)将k顶点并入辅助数组顶点并入及最小边的重新选择：strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj.adj;closedgej.lowcost=G.arcskj.adj;结束图2.3生成树模块3.顶点定位模块：程序默认顶点是从第一个顶点开始的，通过( strcmp(u,G.vexsi)判断出输入的顶点是否是属于G中的元素，如果是则返回该顶点在一维数组中的具体位置，如果不在G中这返回-1.实现流程图如下：值传递（G，u）strcmp(u,G.vexsi) = 0return ir

7、eturn -1YN图2.3顶点定位模块结束结束4.寻找最小权值模块:该模块同样借助与辅助数组进行，首先找到一个权值不为0的顶点，利用一个for(j=i+1;j0)判断权值是否符合条件又利用if(minSZj.lowcost)进而筛选出一个顶点的最小权值，并返回该顶点在数组中的位置K返回到生成树模块。 开始值传递miniside(sz)22while(!SZi.lowcost)i+min=SZi.lowcost;k=ifor(j=i+1;j0minSZj.lowcost)min=SZj.lowcost;k=j;YNNYreturn k;图2.3 寻找最小权值模块3 测试/运行结果1.例如输入图

8、2.2生成树模块具体实现的演示操作的第一步图后的运行结果如下：运行结果与图2.2生成树模块具体实现的演示操作第三步结果完全吻合。2.例如输入如下无向图：V1V4V3V6V7V5V272114300279238151006图3.1图3.1的预期生成树为：V1V3V4V6V7V5V271423106图3.1的预期生成树输入图3.1，运行结果如下：运行结果和图3.1的预期生成树完全符合。参考文献1 严蔚敏，吴伟明. 数据结构（c语言版）M. 北京：清华大学出版社，20062 吕国英，算法设计与分析M. 北京：清华大学出版社，20063 徐宝文，李志. C程序设计语言M. 北京：机械工业出版社，200

9、44 宁正元，王秀丽，林大辉. 算法与数据结构习题精解和实验指导. 北京：清华大学出版社，2007年1月 附 录#include#include #include#include#include #define MAX_VERTEX_NUM 20/ 最大顶点个数#define INFINITY INT_MAX/ 用整型最大值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_VERTEX_NUM;/ 邻接矩阵的数据结构typedef structVRType adj; ArcCell, AdjMatrixM

10、AX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量AdjMatrix arcs;/ 邻接矩阵int vexnum,/ 图的当前顶点数arcnum;/ 图的当前弧数 MGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int LocateVex(MGraph G,V

11、ertexType u)int i;for(i=0;iG.vexnum; +i)if( strcmp(u,G.vexsi) = 0)return i;return -1;/ 采用数组(邻接矩阵)表示法,构造无向网G。int CreateAN(MGraph *G)int i,j,k,w;VertexType va,vb;printf(请输入无向网G的顶点数,边数:(空格区分) n);scanf(%d %d,&(*G).vexnum,&(*G).arcnum); printf(请输入%d个顶点的值:n,(*G).vexnum);for(i=0;i(*G).vexnum;+i) / 构造顶点向量 s

12、canf(%s,(*G).vexsi);for(i=0;i(*G).vexnum;+i) / 初始化邻接矩阵 for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=INFINITY; / 网初始化为无穷大 printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,(*G).arcnum);for(k=0;k(*G).arcnum;+k)scanf(%s%s%d,va,vb,&w); i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.adj=(*G).arcsji.adj=w; / 无向图的反向弧ret

13、urn 1;/ 求领接顶点权值最小边int minimum(minside SZ,MGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一个不为0的值 k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k; / 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void MiniSpanTree_PRIM(MGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(

14、G,u); for(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; / 初始,U=u printf(最小生成树的各条边为:n);for(i=1;iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k=minimum(closedge,G); / 求出T的下一个结点：第K顶点 printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 输出生成树的边 closedgek.lowcost=0; / 第K顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj.adj请输入一个连通图,否则程序无效!n);CreateAN(&G);MiniSpanTree_PRIM(G,G.vexs0); 课程设计总结：经过几天的课程设计，发现了自己很多需要改进的地方，也了解到了一些思考问题的方法。有很多知识都是课堂上所学不到的，不论是请教同学还是自己翻阅资料，收获了知识就是对于自己的一种鼓舞。对于学习计算机来说，算法和自己的编程能力都是很重要的。而这些恰恰是我