软件综合实习报告

　软件综合实习报告

　 题目：最小生成树算法

　院（系）：

　计算机学院

　 专

　业：

　计算机科学与技术

　姓

　名：

　班级学号：

　2012 年 9 月 12 日

　目录 一 ． 系统需求分析与总体设计

　............................................................................ 1

　1.1 需求分析 ……………………………………………………………………………………………………………… 1

　1.1.1 问题描述…………………………………………………………………………………………………………1

　1.1.2 问题分析…………………………………………………………………………………………………………1

　1.1.3 方案选择…………………………………………………………………………………………………………1

　 1.1.4 开发平台…………………………………………………………………………………………………………2

　 1.2 系统总体设计 ……………………………………………………………………………………………………. 2

　二 ． 详细设计与系统实现

　....................................................................................... 2

　2.1 Prime 算法动态演示模 ……. ……………….……………………………………………………………. 2

　 2.1.1 基本思想…………………………………………………………………………………………………………2

　2.1.2 设计与实现……………………………………………………………………………………………………..3

　 2.2

　 Kruskal 算法动态演示模块 ………………………………………………………………………. 4

　 2.2.1 基本思想…………………………………………………………………………………………………………4

　2.2.2 设计与实现………………………………………………………………………………………………………4

　 2.3

　并查集实现 kruskal 算法动态演示模块 ……………………………………………….. 4

　 2.3.1 基本思想…………………………………………………………………………………………………………5

　2.3.2 设计与实现………………………………………………………………………………………………………5

　 2.4 深 度优先搜索实现 Kruskal 算法动态 演示模块 ………………………………. 6

　 2.4.1 基本思想…………………………………………………………………………………………………………6

　2.4.2 设计与实现………………………………………………………………………………………………………7

　 2.5

　广度优先搜索实现 Kruskal 算法动态演示模块 ………………………………. 7

　 2.5.1 基本思想…………………………………………………………………………………………………………7

　2.5.2 设计与实现………………………………………………………………………………………………………8

　 2.6 画图模块 ……………………………………………………………………………………………………………….. 8

　三 ．系统测试

　.................................................................................................................. 9

　3.1 测试数据 ……………………………………………………………………………… 9

　3.2Primme 的测试结果 ………………………………………….…………………… 9

　3.2Kruskal 算法的测试结果 ………………………………………….………..…. 10

　3.3 并查集实现Kruskal 算法的测试结果 ……………………………………. 10

　3.4 深度优先搜索实现Kruskal 算法的测试结果 …………………………. 11

　3.5 广度优先搜索实现Kruskal 算法的测试结果 …………………………. 11

　3.6 效率分析 ……………………………………………………………………………. 12

　四 ． 总结

　........................................................................................................................... 12

　参考资料 ……………………………………………………………………………………………………………………. 13

　一． 系统需求分析与总体设计 1 1.1 需求分析

　1.1.1 问题描述 在一个具有几个顶点的连通图 G 中，如果存在子图 G" 包含 G 中所有顶点和一部分边，且不形成回路，则称 G" 为图 G 的生成树，代价最小生成树则称为最小生成树（Minimal Spanning Tree）。

　许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在 n 个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

　基本的要求是实现两种算法：通过实现Kruskal算法和Prim算法来得到图的最小生成树。并对两种算法进行分析和比较。较高的要求是在边通分量的查询与合并的过程中，采用广度优先搜索算法（Breadth First Search）、深度优先搜索算法(Depth First Search)和并查集（Union-Find Set）这三种方法，并进行分析和比较算法时间复杂度。

　测试数据如下：

　图（1）

　1.1.2 问题分析 通过问题的描述，可知这一道题目主要涉及，面向对象的分析与设计，数据结构和算法。通过这些利用知识实现 Kruskal 算法和 Prim 算法从而得到图的最小生成树。除此之外，在最小生成树的求解过程中会对边通分量进行查询和合并，由题可知要对边通分量进行查询和合并要使用广度优先搜索算法（Breadth First Search）、深度优先搜索算法(Depth First Search)和并查集（Union-Find Set）这三种方法。

　为了更好、更生动的表示这些算法的运算过程，在这里如果使用动态显示算法的求解过程将会是最好的选择。对于不同的算法其求解最小生成树时运算的效率是不同的，因此还需要对各种算法时间复杂度进行分析和比较，从而更加深入的理解算法，从而方便我们在不同的场合采用不同的实现算法。

　1.1.3 方案选择 通过对题目的分析，对于如何将广度优先搜索算法（Breadth First Search）、深度优先搜132 5 4 6 5 6 5 2 4 4 7

　3 1 7 1

　索算法(Depth First Search)和并查集（Union-Find Set）这三种方法运用到对边通分量进行查询和合并中有不同的结合方法。在这里我选择了将这三种搜索算法融合到 Kruskal 算法，因为我觉得在 Kruskal 算法对边通分量进行查询和合并中使用这三种方法更合理且更容易实现，因此也实现了将这三种搜索算法融合到 Kruskal 算法从而实现对图的最小生成树的查找。

　对于运用图形学的知识实现算法的动态运行效果。可以知道使用 MFC 通过单文档画图来实现算法动态显示运行效果或者使用对话框来实现算法动态显示运行效果，为了方便起见，我选择的是通过 MFC 建立单文档来实现这一效果。

　1.1.4 开发平台 使用的系统是 Windows07 ， 开发工具 VC++6.0 2 1.2 系统总体设计

　由于这是对图进行相关的操作，因此涉及图的存储问题，在这里使用的是邻接矩阵这一数据结构来实现图的存储。在对图进行相关操作寻找最小生成树时，得到的生成树中的边采用的是结构体的存储方式，在实现的过程中相关变量和数据的存储也主要通过数组、结构体来实现了。

　在深度优先搜索算法（Breadth First Search）中使用了栈这一数据结构来实现边的连通分量的查询，对广度优先搜索算法(Depth First Search)的实现使用了队列这一数据结构，这里的队列和栈都是通过编程实现。

　这里主要分为六个模块，即 prime 算法模块、kruskal 算法模块、用并查集实现 kruskal算法的模块、kruskal 算法和深度优先搜索算法结合的模块、kruskal 算法和广度优先搜索算法结合的模块以及画图操作的相关模块。设计与实现中由于所体现的重点不同，因此下面的说明主要围绕着此题的重点，即最小生成树的生成过程。

　对于最小生成树生成过程中边相关变量的存储均是通过定义一个边（edge）的结构体变量进行存储的，而关于点的存储则是通过定义数组进行相应的存储，由于不同的实现方法采用的初始值不一样，因此使用的数组会有所不同。

　对于算法运行时的动态显示运行过程这一要求主要通过将相关的画圆、画线等相关画图的操作扦插到相关的算法中，在算法的运行过程中再通过对相关条件的判断从而决定是否执行画圆、画线等操作。在这些算法运行过程中实现的画图操作主要通过调用一个公用的函数进行画图的相关操作。

　二． 详细设计与实现 e 2.1 Prime 算法动态演示模块

　2.1.1 基本思想

　 Prime 算法的基本思想是以图中的某一个顶点作为起始顶点，然后从起始顶点出发不断 的从还没有遍历到的顶点中选择与已经遍历到的顶点存在之间权值最小边的顶点，并将新遍历的点不断的添加到已经遍历的顶点集合中。通过这样的一个遍历过程与画图的相关操作结合来实现最小生成树生成过程的动态演示。

　 对于无向连通图 G（V,E），在 prime 算法中，将图 G 顶点集合分为两个集合 V1（G）和V2（G），V1（G）用来存储当前已经遍历到的顶点，即最小生成树中的顶点 V(MST)，V2（G）

　用来存储还没有遍历到的顶点。对于已经选择的顶点之间的边存储在最小生成树的边的集合中 E(MST)。

　Prime 算法的具体过程如下：

　设最小生成树中点的集合 V(MST)和边的集合 E(MST)的初态均为空。首先从图 G 的顶点 集 V(G)中任选一个顶点，把它加到最小生成树 MST 的顶点集 V(MST)中。然后，依次选出 n-1条符合以下条件的边(vi,vj)。

　（1）(vi,vj)?E(G)，v 是 V(MST)的顶点，而 vj 是还未加入 V(MST)的顶点。此时(vi,vj) 一定均未加入 E(MST)。通过判断先找出所有这样的边 。

　（2）(vi,vj)是关联于 V(MST)中顶点的边中权值最小的边。选出满足该条件的边，将

　 vj 加入 V(MST)，(vi,vj)加入 E(MST) ，之后画出相应的边和新添加进去的顶点。

　下面主要通过题目中给出的例子（如图 1）对 prime 算法进行详细的解析：

　（1）将 1 作为起始顶点添加到 V(MST)，找到与之相连的符合条件的边(v1,v2)，将权值为 5 的边添加到 E(MST)中，并将顶点 2 添加到 V(MST)中并画出此边。

　（2）集合 V(MST)此时已经有两个顶点了，即 1、2，找到与之相连的符合条件的边(v2,v3) 将权值为 1 的边添加到 E(MST)中，并将顶点 3 添加到 V(MST)中并画出此边。

　（3）集合 V(MST)此时已经有三个顶点了，即 1、2、3，找到与之相连的符合条件的边(v2,v4)将权值为 2 的边添加到 E(MST)中，并将顶点 4 添加到 V(MST)中并画出此边。

　（4）集合 V(MST)此时已经有四个顶点了，即 1、2、3、4，找到与之相连的符合条件的边(v4,v5)将权值为 3 的边添加到 E(MST)中，并将顶点 5 添加到 V(MST)中并画出此边。

　（5）集合 V(MST)此时已经有五个顶点了，即 1、2、3、4、5，找到与之相连的符合条件的边(v4,v6)将权值为 4 的边添加到 E(MST)中，并将顶点 6 添加到 V(MST)中并画出此边。

　（6）集合 V(MST)此时已经有六个顶点了，即 1、2、3、4、5、6，找到与之相连的符合条件的边(v6,v7)将权值为1的边添加到E(MST)中，并将顶点7添加到V(MST)中并画出此边。

　至此图 G 中所有的点均已添加到了 V(MST)，最小生成树生成完毕，其权值为 16。

　2.1.2 设计与实现 对于 prime 算法的动态演示，主要是关乎两个函数的实现一个是画图函数的实现，另 外一个就是如何判断何时进行画图操作并进行相关操作的画图函数，在这里主要通过两个函数实现一个是与 Kruskal 算法动态实现的公用的画图操作函数，另外一个就是 prime 算法寻找最小生成树的实现。这里仅给出语言描述的实现过程，源代码的实现在后面的附录中将会给出。

　Prime 算法的设计与实现 如下所述：

　（1）对所画区域刷新。

　（2）

　MST 顶点初始值={序号为 0 的顶点}，其边所在的结构体数组 E[n-1]的值也为空。lowCost的初始值为邻接矩阵中第0行的值，这样初始时lowCost中就存放了从集合V(MST)中顶点 0 到集合 V(G)－V(MST)中各个顶点的权值 。

　（3）循环 n-1 次 2.1 从 lowCost 中寻找具有最小权值的边。根据 lowCost 的定义，这样的边其一个顶点必然为集合 V(MST)中的顶点，其另一个顶点（设第 k 个顶点）必然为集合 V(G)－V(MST)中的顶点 ，将相应的边添加到 E[n-1]中。

　2.2 存第 k 个顶点的数据和相应边的权值到 MST 中，并将 lowCost[k]置为-1，表示第k 个顶点从集合 V(G)－V(MST)加入了集合 V(MST)中

　2.3 当第 k 个顶点加入到集合 V(MST)后，若存在一条边(k,j)，其中 k 是集合 V(MST)的顶点，j 是集合 V(G)－V(MST)的顶点，且边(k,j)权值较原先 lowCost[j]的代价更小，则用这个权值修正原先 lowCost[j]中的权值。

　2.4 当最小生成树生成完毕时，则调用 Draw（E）函数画出生成的过程。

　l 2.2 Kruskal 算法动态演示模块

　2.2.1 基本思想 Kruskal 算法通常是在已知 V(MST)=V(G)，E(MST)的初态为空时对图 G 进行相关处理的到最小生成树的。首先将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边。每次挑选边成功了即画出此边。在 n 个顶点的图中，选够 n-1 条边即可。具体如下：

　（1）

　构造一个只有 n 个顶点没有边的非连通图 T，图中的每个顶点为一个连通分量。

　（2）

　在原图 G 中的边中选择具有最小权值的边，若该边的两个顶点落在不同的连 通分量上，则将此边加入到 T 中；否则，则将此边舍去（此后永不选入此边），重新选择一条权值最小的边并进行画图的操作处理。

　（3）如此反复下去，直到所有顶点在同一个连通分量上为止。

　下面主要通过题目中给出的例子（如图 1）对 kruskal 算法进行详细的解析：

　（1）在图 G 的边的集合 E 中按存储次序选择权值最小的边，即（2,3）由于边（2,3）在（6,7）前面存储，所以此处选择的边（2,3）并画出此边，其权重为 1。

　（2）在图 G 的边的集合 E 中按存储次序选择权值最小的边，即（6,7）由于边（6,7）在（2,3）后面存储，所以后选择边（6,7）并画出此边，其权重为 1。

　（3）在图 G 的边的集合 E 中选择权值最小的边（2,4）并画出此边，其权重为 2。

　（4）在图 G 的边的集合 E 中选择权值最小的边（4,5）并画出此边，其权重为 3。

　（5）在图 G 的边的集合 E 中选择权值最小的边（4,6）并画出此边，其权重为 4。

　（6）在图 G 的边的集合 E 中选择权值最小的边（1,2）并画出此边，其权重为 5。

　至此通过 kruskal 算法得到最小生成树及生成过程，其最小生成树的权值为 16。

　2.2.1 模块设计与实现 Kruskal 算法的实现主要包含两个部分，即带权值的边的排序和判断选取的边的两个顶点是否属于同一个连通分量。因此首先将图 G 的顶点集合 V 分为 n 个等价类，每个等价类包括一个顶点；然后以权值的大小为顺序处理各条边，如果某条边连接两个不同等价类的顶点，则这条边被添加到 MST（选取的边不与前面选取的边构成回路），两个等价类被合并为一个；反复执行此过程，直到只剩下一个等价类。

　kruskal 算法的设计与实现如下所述（具体的代码实现见附录）：

　（1）对所画区域进行刷新。

　（2）设置查找到的顶点集合 find[n]所有的值为-1，存储边的集合 E[n-1]为空集。

　（3）判断找到的边的数目是否小于顶点的数目减一，即 n-1，如果是则从没有被选中的边中选取权值最小的边，如果放入存储边的集合中不构成回路则添加进去，否则舍去此边。

　（4）如果不符合（2）中的判断则不断的重复直到选取的边等于 n-1。

　（5）当最小生成树生成完毕时，则调用 Draw（E）函数画出生成的过程。

　3 2.3 并查集实现 l kruskal 算法动态演示模块

　2.3.1 基本思想 并查集处理问题的主要思想是在处理时使用搜索与合并运算对相关集合进行处理。最初 把每一个对象看做是一个单元集合，然后依次按顺序读入一个等价对后，将等价对中的两个元素所在的集合合并。在此过程中不断的重复使用一个搜索运算，从而确定此元素在哪一个集合中，当读入一个等价对 A≡B 时，首先检测 A 和 B 是不是属于同一个集合，如果是，则不用合并；如果不是，则使用一个合并运算把 A 和 B 合并到同一个集合中，使得这两个集合中的任意两个元素都是等价的（依据等价的传递性）。

　在此处实现 Kruskal 算法时主要使用并查集对相关顶点进行搜索和合并，从而实现了使用并查集实现 Kruskal 算法。在程序中也实现了并查集的动态演示，通过 Kruskal 算法调用并查集的函数，在函数中 对相关的顶点信息进行判断从而实施相应的画图操作。

　下面通过题目的例子（如图 1）对 kruskal 算法利用并查集实现过程中相应集合的变化进行了详细的解析：

　（1）最初的集合有 7 个，这 7 个集合中均只有一个元素分别为{1}、{2}、{3}、{4}、{5}、{6}、{7}。画出初始状态。

　（2）在图 G 的边的集合 E 中按存储次序选择权值最小的边，即（2,3）由于边（2,3）在（6,7）前面存储，所以此处选择的边（2,3）其权重为 1。此时集合变为{1}、{2、3}、{4}、 {5}、{6}、{7}。通过判断画出发生改变的集合{2、3}。

　（3）在图 G 的边的集合 E 中按存储次序选择权值最小的边，即（6,7）由于边（6,7）在（2,3）后面存储，所以后选择边（6,7），其权重为 1。此时集合变为{1}、{2、3}、{4}、 {5}、{6、7}。通过判断画出发生改变的集合{6、7}。

　（4）在图 G 的边的集合 E 中选择权值最小的边（2,4）并画出此边，其权重为 2。此时集合变为{1}、{2、3、4}、{5}、{6、7}。通过判断画出发生改变的集合{2、3、4}。

　（5）在图 G 的边的集合 E 中选择权值最小的边（4,5）并画出此边，其权重为 3。此时集合变为{1}、{2、3、4、5}、{6、7}。通过判断画出发生改变的集合{2、3、4、5}。

　（6）在图 G 的边的集合 E 中选择权值最小的边（4,6）并画出此边，其权重为 4。此时集合变为{1}、{2、3、4、5、6、7}。通过判断画出发生改变的集合{2、3、4、5、6、7}。

　（7）在图 G 的边的集合 E 中选择权值最小的边（1,2）并画出此边，其权重为 5。此时集合变为{1、2、3、4、5、6、7}。通过判断画出发生改变的集合{1、2、3、4、5、6、7}。

　至此 kruskal 算法利用并查集查找、合并的过程结束，通过 kruskal 算法得到最小生成树及生成过程，其最小生成树的权值为 16。

　2.3.2 设计与实现 Kruskal 算法利用并查集实现查找、合并的设计与实现也是首先选择权值最小的边，其次是利用并查集来对所要选择的那些顶点进行查找、合并。在 Kruskal 使用并查集时首先对其进行边集合的排序，接着利用并查集对图 G 中的顶点进行初始化，每一个顶点当做一个集合，同时给其一个相关的变量标志其集合中顶点的数目；然后利用并查集判断此时的顶点所在集合是不是相同，如果不相同则合并这两个顶点所在的集合。

　并查集的实现主要包含三个方面，即并查集的初始化、查找和集合的合并，下面主要介绍并查集这三个过程的设计与实现。

　（1）对所画区域进行刷新。

　（2）初始化过程：为了方便并查集的描述与实现，通常把先后加入到一个集合中的元素表示成一个树形结构，并用根节点来代表这个集合。这里定义一个 parent[n]的数组，parent[i]中存储的就是结点 i 所在的树中的结点 i 父亲结点的序号，并查集的初始化中所有的

　结点的 parent 值均为-1，即每个结点就是根节点，只包含它本身这一个元素。

　（3）查找：主要是查找并返回结点 i 所属集合的根节点。在此函数中如果只靠一个循环来得到结果，则对于合并中得到的层次比较深的集合，查找会很费时。这里通过压缩路径的方法来加快后续的查找速度，主要是通过增加一个 while 循环，每次都把从结点 i 到集合根节点的路径上经过的结点直接设置为根结点的子结点。

　（4）合并：两个集合合并时，任何一方均可作为另一方的子孙。在这里采用的是加权合并，即把两个集合中元素个数少的根结点作为元素个数多的根节点的子结点。这样处理可以减少树中深层次元素的个数，减少后续查找时间。在每一次的合并过程结束时，将会画出合并之后的集合。

　2.4 深度优先搜索实现 l Kruskal 算法动态演示模块

　2.4.1 基本思想 深度优先搜索主要是在图的遍历中使用此方法对整个图进行遍历来访问整个图中所有节点的一种遍历方法。通常是利用递归来实现图中结点的遍历。其基本思想是：对于一个无向连通图，从某一个起始结点 vi 出发，访问与它相连的一个结点 vj，且 vi、vj 这两个结点之间的边（vi、vj）是所有以 vi 为连接结点的边中权值最小的；然后再从 vj 出发寻找与 vj 相连的顶点，且它们之间的边是所有以 vi 为连接结点的边中权值最小的，不断的重复直到找到访问完所有的结点为止。

　在这个算法的实现过程中，边通分量的查找虽然是深度优先搜索为主，但是是以最小生成树的的生成过程为主，因此这里所采用的画图操做运行的情况和使用一般的方法实现kruskal 算法的运行过程是一样的，在这里不再给予详细的说明，如有必要则可以参照 kruskal的生成最小生成树的过程。对于深度优先搜索方法的实现这里使用的方法是通过利用栈这一数据结构来实现的。下面仅给出在边已经通过权值大小进行排序之后，边通分量的查找的过程和查找之后集合的合并情况 （1）得到图 G 中最小权值的边（2,3），因为（2,3）排在（6,7）的前面，所以先判断它的两个结点，判断点 2 和点 3 是否已经访问过了，由于数组 check 中相应的值为 0，说明没有被访问过，因此合并这两个结点为一个集合{2、3}。同时通过深度优先搜索对这两个结点分别进行判断及标记已经访问过了。

　（2）继续向下查找得到边（6,7），判断点 6 和点 7 是否已经访问过了，由于数组 check中相应的值为 0，因此合并这两个结点，得到新的集合{6、7}。同时通过深度优先搜索对这两个结点分别进行判断及标记已经访问过了。

　 （3）继续向下查找得到边（2,4），判断点 2 和点 4 是否已经访问过了得知点 2 已经被访问过了，点 4 没有，因此得到新的集合{2,、3、4}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记，可知点 4 此时被标记访问过了。

　 （4）继续向下查找得到边（4,5），判断点 4 和点 5 是否已经访问过了得知点 4 已经被访问过了，点 5 没有，因此得到新的集合{2,、3、4、5}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记，可知点 5 此时被标记访问过了。

　（5）继续向下查找得到边（4,6），判断点 4 和点 6 是否已经访问过了得知点 4 已经被访问过了，点 6 没有，因此得到新的集合{2,、3、4、5、6、7}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记则知均不需要。

　（6）继续向下查找得到边（5,6），判断点 5 和点 6 是否已经访问过了得知已经被访问过了，因此得到不进行集合的合并，继续向下查找相应的边。

　（7）继续向下查找得到边（1,2），判断点 1 和点 2 是否已经访问过了得知点 2 已经被

　访问过了，点 1 没有，因此得到新的集合{1、2,、3、4、5、6、7}。同时通过深度优先搜索对着两个结点分别进行判断是否需要标记，可知点 1 此时被标记访问过了。

　至此通过利用深度优先搜索进行边通分量查询的 kruskal 算法运行完毕，通过对比可知和使用普通的查找算法得到的运行结果是一致的。

　2.4.2 设计与实现 在这里采用 Kruskal 算法得到最小生成树的过程中，在对边连通分量的查询时使用了深度优先搜索的方法来查询当前得到的具有最下权值的边的两个顶点是不是已经存在于被访问过的结点的集合中，如果是的则进行下一次查询，否则的话则将没有访问过的结点加入已经访问过的结点的集合中。

　深度优先搜索的实现主要利用栈这一数据结构来实现。因此主要包含两个方面，即栈这一数据结构中相关函数的设计与实现，以及如何实现深度优先搜索算法判断变量通分量的设计与实现。由于对栈已经比较熟悉，在这里仅作简要的说明。

　（1）栈：

　这里使用到的与栈相关的操作主要有栈中数据的初始化 StackInitiate、将数据压入栈的操作 StackPush、将数据弹出栈的操作 StackPop、判断栈是否为空的操作StackNotEmpty 和得到栈顶元素的操作 StackTop。

　（2）查找与合并：在深度优先搜索中首先判断是否需要标记此节点，如果需要标记此节点则将此节点标记为以访问过，并添加到已经访问过的结点的集合中，并将相应的边存入E[]中；如果是要进行判断两个结点是不是都已经访问过了，及是否属于同一个集合利用栈来不断的搜索其中一个结点所在的集合中是否有另一个结点，如果存在则舍弃当前所选择的边，否则选择此边为最小生成树的一边。

　下面给出 kruakal 算法利用深度优先搜索进行边连通分量查询和合并从而得到最小生成树的的设计与实现步骤：

　（1）对所画区域进行刷新。

　（2）对已经排好序的边进行选择，对没有访问过的最小权值的边的两个结点进行判断，检查是否已经被访问过了，如果有一个没有被访问过，则将和此边相应的顶点进行深度优先搜索的判断之后进行标记，同时存储所选择的这个边和相应的顶点。

　（3）如果都已经被访问过了，则利用深度优先搜索判断这两个节点是否属于同一个集合，如果是的话则抛弃此边，如果不是的话则对其进行标记，并画出此边和相对应的点。

　（4）选择下一条没有被访问过的边重新进行（1）、（2）的判断，直到所有的顶点均已被访问过且在同一个集合中，即已经添加到了最小生成树中则最小生成树生成完毕。

　（5）当最小生成树生成完毕时，则调用 Draw（E）函数画出生成的过程。

　2.5 广度优先搜索实现 l Kruskal 算法动态演示模块

　2.5.1 基本思想 广度优先搜索主要是在图的遍历中使用此方法对整个图进行遍历来访问整个图中所有节点的一种遍历方法。通常是利用队列这一数据结构来实现图中结点的遍历。其基本思想是：对于一个无向连通图，从某一个起始结点 vi 出发，依次访问与它相连的所有未访问过的结点 vj1、vj2……vjn，然后在顺序访问 vj1、vj2……vjn 的所有还未访问过的邻接顶点；再从这些邻接顶点出发，再访问它们的所有未访问过的邻接顶点，……，不断重复直到图 G 中所有的顶点都被访问过为止。

　kruskal 算法利用广度优先搜索进行边通分量的查询和合并的的实现过程中，边通分量的查找和合并虽然是广度优先搜索为主，但是总体是以最小生成树的的生成过程为主，因此

　这里所采用的画图操做运行的情况和使用一般的方法实现 kruskal 算法的运行过程是一样的，在这里不再给予详细的说明，如有必要则可以参照 kruskal 的生成最小生成树的过程。对于广度优先搜索方法的实现这里使用的方法是通过利用队列这一数据结构来实现的。

　这里采用的广度优先搜索主要是用来检索边的邻接顶点是不是在同一个集合中，由于使用 kruskal 算法时最初已经对边进行了一个排序，所以每一次所选用的边和通过广度优先搜索对邻接顶点进行判断的结果是一样的，在这里不再给予详细的说明，kruskal 算法结合广度优先搜索具体的运算过程和 kruskal 算法结合深度优先搜索的运算过程是一样的，在这里不再列出。由于本题的重点是最小生成树的生成，在这里不再给出广度优先搜索具体的搜索过程。

　2.5.2 设计与实现 在这里采用 Kruskal 算法得到最小生成树的过程中，在对边连通分量的查询时使用了广度优先搜索的方法来查询当前得到的具有最下权值的边的两个顶点是不是已经存在于被访问过的结点的集合中，如果是的则进行下一次查询，否则的话则将没有访问过的结点加入已经访问过的结点的集合中。

　广度优先搜索的实现主要利用队列这一数据结构来实现。因此主要包含两个方面，即队列这一数据结构中相关函数的设计与实现，以及如何实现深度优先搜索算法判断变量通分量的设计与实现。由于对队列已经比较熟悉，在这里仅作简要的说明。

　（1）队列：

　这里使用到的与队列相关的操作主要有栈中数据的初始化 QueueInitiate、将数据存入队列的操作 QueueAppend、将数据从队列中删除的操作 QueueDelete、判断队列是否为空的操作 QueueNotEmpty。

　（2）查找与合并：在广度优先搜索中首先判断是否需要标记此节点，如果需要标记此节点则将此节点标记为以访问过，并添加到已经访问过的结点的集合中；如果是要进行判断两个结点是不是都已经访问过了，及是否属于同一个集合利用栈来不断的搜索其中一个结点所在的集合中是否有另一个结点，如果存在则舍弃当前所选择的边，否则选择此边为最小生成树的一边。

　下面给出 kruakal 算法利用广度优先搜索进行边连通分量查询和合并从而得到最小生成树的的设计与实现步骤：

　（1）对所画区域进行刷新。

　（2）对已经排好序的边进行选择，对没有访问过的最小权值的边的两个结点进行判断，检查是否已经被访问过了，如果有一个没有被访问过，则将和此边相应的顶点进行广度优先搜索的判断之后进行标记，同时画出所选择的这个边和相应的顶点。

　（3）如果都已经被访问过了，则利用广度优先搜索判断这两个节点是否属于同一个集合，如果是的话则抛弃此边，如果不是的话则对其进行标记，并画出此边和相对应的点。

　（4）选择下一条没有被访问过的边重新进行（1）、（2）的判断，直到所有的顶点均已被访问过且在同一个集合中，即已经添加到了最小生成树中则最小生成树生成完毕。

　（5）当最小生成树生成完毕时，则调用 Draw（E）函数画出生成的过程。

　2.6 画图模块

　这一模块主要是实现如何动态的演示程序运行的效果，主要涉及的有三个方面，第一个方面是使用不同的算法实现最小生成树的绘制过程，第二个方面是画图区域的刷新，第三个方面是并查集的绘制过程。

　对于最小生成树的绘制过程有一个函数承担，主要是实现程序在调用 prime 算法、kruskal 算法、深度优先搜索实现的 kruskal 算法和广度优先搜索实现的 kruskal 算法的过程中

　相关运行过程的绘制，此处主要通过判断最小生成树中所存储的边来进行绘制。

　画图区域的刷新主要是为了实现同一块区域可以画多次不同的运行过程，有两个函数承担。由于并查集的绘制和最小生成树的绘制没有太大的关联，因此在这里采用了单独绘制并查集实现 kruskal 算法中并查集的合并过程。

　三． 系统测试 3.1 测试数据

　 图（2）

　上图是利用程序直接得到的原图形，此测试数据中有七个顶点，有十条边。通过这些可知其生成的最小生成树只能有七个顶点、六条边。通过观察可知这六条边应为（2,3）、（6,7）、（2,4）、（4,5）、（4,6）、（1,2）。

　3.2Primme 的测试结果

　 图（3）

　通过上面 prime 算法的解析结果和运行结果发现其运行结果与分析中应该得到的结果是一致的，由于画图和判断中采用的有延长运行时间的函数，因此这里只通过理论分析得出prime 算法的运行效率。

　 3.2Kruskal 算法的测试结果

　 图(4)

　 通过上面 kruskal 算法的解析结果和运行结果发现其运行结果与分析中应该得到的结果是一致的，由于画图和判断中采用的有延长运行时间的函数，因此这里只通过理论分析得出kruskal 算法的运行效率。

　3.3 并查集实现 Kruskal 算法的测试结果

　图(5)

　 此图中首先给出了最初集合的状况，紧接着给出了每一次进行边通分量查找合并过程中发生变化的集合的状况。通过此图并结合上面对并查集的分析可知与其运行一致。

　3.4 深度优先搜索实现 Kruskal 算法的测试结果

　图（6）

　在这里没有对深度优先搜索的过程给予动态显示，主要是模拟了深度优先搜索实现kruskal 算法的过程，也即最小生成树的生成过程。通过对比前两种 kruskal 算法的实现过程可知其运行是一致的。

　3.5 广度优先搜索实现 Kruskal 算法的测试结果

　图（7）

　 通过与其他方法实现 kruska 算法进行对比，可知结果是一致的。由此也说明一个问题，即对于使用不同的方法来实现这一算法，改变的只是其效率，但是整体的运行情况是不会发生改变的。因此在实现的过程中应该尽量选择效率比较高的方法来实现算法。

　对于广度优先搜索每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接 点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅在于对顶点访问的顺序不同。对于使用 kruskal 算法和深度优先搜索结合的算法，对边的遍历至多是 e 次，故其总代价为 O(n^2*e)。

　3.6 效率分析 Prime 算法实现的函数主要是一个两重循环，其中每一重循环的次数均为顶点个数 n，所以该算法的时间复杂度为 O(n^2)。

　Kruskal 算法的时间复杂度与选取的排序函数有关，这里采用的是不是对其进行排序 而是在每一次循环中找余下的边中权值最小的边，找到最小的边之后将对其相应的点进行标记，已知点的个数为 n 边的个数为 e，所以它的时间复杂度为最坏的情况下为 O(e^2)，如果边已经很有序的话，也就是最好的情况下的时间复杂度为 O(n^2)。

　Kruskal 运用并查集实现中使用了路径压缩，Find 和 UNION 函数几乎是常数假设可能对几乎所有边都判断过了，则最坏情况下算法时间代价为 O(eloge)，即堆排序的时间通常情况下只找了接近顶点数目那么多边的情况下，MST 就已经生成，时间代价接近于 O(nloge)

　 深度优先搜索对每一条边处理一次，每个顶点访问一次以邻接矩阵作存储结构：处理所 有的边需 O(n n^2)的时间 ，故总代价为 O(n^2)。对于使用 kruskal 算法和深度优先搜索结合的算法，对边的遍历至多是 e 此故其总代价为 O(n^2*e)。

　四． 总结 这个题目的主要要求是通过使用不同的算法求出图的最小生成树，并且通过画图动态的显示出来其不同的算法在求解最小生成树时的运行步骤。在我的程序中已经实现了对给出的这一例子使用 Prime 算法、Kruskal 算法求解最小生成树的运算过程的动态显示，除此之外，对于还实现了在边通分量的查询与合并的过程中，采用广度优先搜索算法（Breadth First Search）、深度优先搜索算法(Depth First Search)和并查集（Union-Find Set）三种方法来实现对此例中图的最小生成树的求解，主要是将这三种搜索方法与 Kruakal 结合来实现对最小生成树的求解。

　 虽然通过例子实现了使用题目中要求的算法来求解最小生成树，但是没能实现给用户一个友好的界面来方便求解各种不同的图的最小生成树，只能通过改变程序里面相关的存储变量来实现对不同图的最小生成树的求解。同时由于对于作图这方面不是很熟练，没能实现对图的动态扩充，所以只能是实现对一定数目，一定边数的图的求解。为了我的程序更加完美我会继续努力，从而实现图的动态扩充，同时让程序更为简练。

　 在最初选择题目的时候，总是觉得自己对使用 MFC 来画图这一方面不是很熟悉，担心自己做不出来。在实现在边通分量的查询与合并的过程中，采用广度优先搜索算法（Breadth

　First Search）、深度优先搜索算法(Depth First Search)和并查集（Union-Find Set）三种方法来实现对此例中图的最小生成树的求解，这一方面最初也是相当的纠结，不知道该从什么方面下手。因为在学习数据结构的时只知道广度优先搜索算法（Breadth First Search）、深度优先搜索算法(Depth First Search)是用来遍历图的，平时没有在搜索的过程中使用此种算法，不知道该从何下手，通过老师的讲解多多少少悟出了点，之后反复的思考最终通过使用队列实现了在边通分量的查询与合并的过程中，采用广度优先搜索算法（Breadth First Search），通过使用栈实现了在边通分量的查询与合并的过程中，深度优先搜索算法(Depth First Search)。

　这让我意识到学习到的知识一定要活用才能创造出更好的方法，只是使用它通常的用途是远远不够的。

　虽然做的时候还是很多都不熟悉，但是我知道如果我不尝试这去做的话就真的什么也做不出来了。虽然最后做的和自己最初设想的有所差异，但是题目中的要求我都完成了，还是小有成就感的。所以通过这次的实习，让我认识到只要去尝试，去努力没有什么是不可以做的。

　 参考文献：

　[1]朱战立，数据结构—使用 c 语言（第四版），电子工业出版社 2010 年 11 月 [2]王桂平、王衍、任嘉辰，图论算法理论、实现及应用，北京大学出版社，2011 年 1 月 [3]孙鑫、余安萍，VC++深入详解，电子工业出版社 2011 年 5 月