数据结构课程设计报告-最小生成树Kruskal算法.doc

课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：最小生成树Kruskal算法 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师：  目 录 1 课程设计介绍 1 1.1 课程设计内容 1 1.2 课程设计要求 1 2 课程设计原理 2 2.1 课设题目粗略分析 2 2.2 原理图介绍 4 2.2.1 功能模块图 4 2.2.2 流程图分析 5 3 数据结构分析 11 3.1 存储结构 11 3.2 算法描述 11 4 调试与分析 13 4.1 调试过程 13 4.2 程序执行过程 13 参考文献 16 附 录（关键部分程序清单） 17  1 课程设计介绍 1.1 课程设计内容 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。 1.2 课程设计要求 顶点信息用字符串，数据可自行设定。 参考相应的资料，独立完成课程设计任务。 交规范课程设计报告和软件代码。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析： 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。 Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下： 初始化。起源点设置为：①ds=0,ps为空；②所有其它点：di=∞,pi=？；③标记起源点s，记k=s，其他所有点设为未标记的。 k到其直接连接的未标记的点j的距离，并设置： dj=min[dj, dk+lkj] 式中，lkj是从点k到j的直接连接距离。 选取下一个点。从所有未标记的结点中，选取dj中最小的一个i： di=min[dj, 所有未标记的点j] 点i就被选为最短路径中的一点，并设为已标记的。 4）找到点i的前一点。从已标记的点中找到直接连接到i的点j*，作为前一点，设置： i=j* 5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。 而程序中求两点间最短路径算法。其主要步骤是： 调用dijkstra算法。 将path中的第“终点”元素向上回溯至起点，并显示出来。 2.2 原理图介绍 2.2.1 功能模块图 图2.1 功能模块图 2.2.2 流程图分析 主函数 图2.2 主函数流程图 insertsort函数 图2.3 insertsort函数流程图 3．Kruskal函数 图2.4 Kruskal函数流程图 4. dijkstra函数 图2.5 dijkstra函数流程图 5. printpath1函数 图2.6 printpath1函数流程图 6. printpath2函数 图2.7 printpath2函数流程图  3 数据结构分析 3.1 存储结构 定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。 struct edges {int bv; int tv; int w; }; 3.2 算法描述 1. Kruskal函数： 因为Kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks，在Kruskal中调用seeks。 2. d