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

沈阳航空航天大学 课 程 设 计 报 告 课程设计题目：图的最少连通路径集 院（系）：计算机学院 专业：计算机科学与技术 班级：***** 学号：***** 姓名：*** 指导教师：许莉 目 录 1 题目的要求和内容 1 1.1图的最少连通路径集 1 1.2课设内容 1 1.3课设要求 1 2 系统功能结构模块图 2 2.1功能模块图 2 2.2生成树模块的具体演示操作 2 2.3模块功能说明 4 3 测试/运行结果 8 参考文献 10 附 录 11 1 题目的要求和内容 1.1图的最少连通路径集 在无向图G中，如果从顶点V到顶点V1有路径，则称V和V1是连通的；如果对于图中任意两点V1，V2都是连通的，则称G是连通图。如果给定一个带权值的图（又叫网）且是一个连通图则该图一定存在最小连通路径集即该图的最小生成树。 1.2课设内容 给定一个无向图，代表一个特定的网络连接关系，现根据这个图求出一组路径，路径中包含节点仅一次，并且途中所有节点至少属于其中一条路径，要求求出的路径集合中包含的路径数量最少。 1.3课设要求 1.利用所学知识，设计相应的数据结构 2.熟练运用开发环境 3.完成软件的设计与编程 4.熟练掌握基本的调试方法 5.提交符合课程设计规范的报告 系统功能结构模块图 2.1功能模块图 本程序由以下几个模块构成 图2.1 系统模块 2.2生成树模块的具体演示操作 1.普利姆算法实现过程演示(寻找最小权值的过程)： 2.3模块功能说明 1.建图模块 通过输入的节点数和弧数来控制输入的节点数和弧数，并通过数组一个一维数组储存顶点和一个二维数组储存弧信息，边信息的储存是一个领接矩阵，领接矩阵的数为无穷大或者为相应的权值，相应流程图如下： 2.生成树模块 此模块采用普利姆算法实现，此算法实现的建立在顶点定位模块和寻找最小权值模块的基础上，首先定位首个顶点（该顶点是程序默认的一维数组的第一个元素），通过定位模块找出顶点在一维数组中的位置，再通过辅助数组与寻找最小权值模块进行比较后将该顶点在领接矩阵中的值赋给辅助数组，最后通过辅助数组用同样的方式找出图中剩余顶点相连的弧的最小权值，然后打印出所有的顶点的最小边即最小生成树实现流程图如下： 3.顶点定位模块： 程序默认顶点是从第一个顶点开始的，通过( strcmp(u,G.vexs[i])判断出输入的顶点是否是属于G中的元素，如果是则返回该顶点在一维数组中的具体位置，如果不在G中这返回-1.实现流程图如下： 4.寻找最小权值模块: 该模块同样借助与辅助数组进行，首先找到一个权值不为0的顶点，利用一个for(j=i+1;jG.vexnum;j++)控制条件进行顶点的移动比较，且通过if(SZ[j].lowcost0)判断权值是否符合条件又利用if(minSZ[j].lowcost)进而筛选出一个顶点的最小权值，并返回该顶点在数组中的位置K返回到生成树模块。 3 测试/运行结果 1.例如输入图2.2生成树模块具体实现的演示操作的第一步图后的运行结果如下： 运行结果与图2.2生成树模块具体实现的演示操作第三步结果完全吻合。 2.例如输入如下无向图： 图3.1的预期生成树为： 输入图3.1，运行结果如下： 运行结果和图3.1的预期生成树完全符合。 参考文献 [1] 严蔚敏，吴伟明. 数据结构（c语言版）[M]. 北京：清华大学出版社，2006 [2] 吕国英，算法设计与分析[M]. 北京：清华大学出版社，2006 [3] 徐宝文，李志. C程序设计语言[M]. 北京：机械工业出版社，2004 [4] 宁正元，王秀丽，林大辉. 算法与数据结构习题精解和实验指导. 北京：清华大学出版社，2007年1月 附 录 #includestdio.h #includestdlib.h #includemalloc.h #includestring.h #includelimits.h #define MAX_VERTEX_NUM 20 // 最大顶点个数 #define INFINITY INT_MAX // 用整型最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_VERTEX_NUM]; // 邻接矩阵的数据结构 typedef struct { VRType adj; }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix ar