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

课 程 设 计 报 告

院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师：

数据结构课程设计 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 课程设计要求

1. 顶点信息用字符串，数据可自行设定。 2. 参考相应的资料，独立完成课程设计任务。 3. 交规范课程设计报告和软件代码。

2 课程设计原理

2.1 课设题目粗略分析

根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：

1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。

2. Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。

3. Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：

1）初始化。起源点设置为：①ds=0,ps为空；②所有其它点：di=∞,pi=？；③标记起源点s，记k=s，其他所有点设为未标记的。 2）k到其直接连接的未标记的点j的距离，并设置： dj=min[dj, dk+lkj]

式中，lkj是从点k到j的直接连接距离。

3）选取下一个点。从所有未标记的结点中，选取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 流程图分析

1. 主函数

图2.2 主函数流程图

2. insertsort函数

3. 图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需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数se …… 此处隐藏：2621字，全部文档内容请下载后查看。喜欢就下载吧 ……