软件综合实习报告

软件综合实习报告题目：最小生成树算法院（系）：计算机学院专业：计算机科学与技术姓名：班级学号：2012年9月12日目录一．系统需求分析与总体设计..........................................................................11.1需求分析………………………………………………………………………………………………………………11.1.1问题描述…………………………………………………………………………………………………………11.1.2问题分析…………………………………………………………………………………………………………11.1.3方案选择…………………………………………………………………………………………………………11.1.4开发平台…………………………………………………………………………………………………………21.2系统总体设计…………………………………………………………………………………………………….2二．详细设计与系统实现.....................................................................................22.1Prime算法动态演示模…….……………….…………………………………………………………….22.1.1基本思想…………………………………………………………………………………………………………22.1.2设计与实现……………………………………………………………………………………………………..32.2Kruskal算法动态演示模块……………………………………………………………………….42.2.1基本思想…………………………………………………………………………………………………………42.2.2设计与实现………………………………………………………………………………………………………42.3并查集实现kruskal算法动态演示模块………………………………………………..42.3.1基本思想…………………………………………………………………………………………………………52.3.2设计与实现………………………………………………………………………………………………………52.4深度优先搜索实现Kruskal算法动态演示模块……………………………….62.4.1基本思想…………………………………………………………………………………………………………62.4.2设计与实现………………………………………………………………………………………………………72.5广度优先搜索实现Kruskal算法动态演示模块……………………………….72.5.1基本思想…………………………………………………………………………………………………………72.5.2设计与实现………………………………………………………………………………………………………82.6画图模块………………………………………………………………………………………………………………..8三．系统测试...............................................................................................................93.1测试数据………………………………………………………………………………93.2Primme的测试结果………………………………………….……………………93.2Kruskal算法的测试结果………………………………………….………..….103.3并查集实现Kruskal算法的测试结果…………………………………….103.4深度优先搜索实现Kruskal算法的测试结果………………………….113.5广度优先搜索实现Kruskal算法的测试结果………………………….113.6效率分析…………………………………………………………………………….12四．总结........................................................................................................................12参考资料…………………………………………………………………………………………………………………….131一．系统需求分析与总体设计1.1需求分析1.1.1问题描述在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树（MinimalSpanningTree）。许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。基本的要求是实现两种算法：通过实现Kruskal算法和Prim算法来得到图的最小生成树。并对两种算法进行分析和比较。较高的要求是在边通分量的查询与合并的过程中，采用广度优先搜索算法（BreadthFirstSearch）、深度优先搜索算法(DepthFirstSearch)和并查集（Union-FindSet）这三种方法，并进行分析和比较算法时间复杂度。测试数据如下：图（1）1.1.2问题分析通过问题的描述，可知这一道题目主要涉及，面向对象的分析与设计，数据结构和算法。通过这些利用知识实现Kruskal算法和Prim算法从而得到图的最小生成树。除此之外，在最小生成树的求解过程中会对边通分量进行查询和合并，由题可知要对边通分量进行查询和合并要使用广度优先搜索算法（BreadthFirstSearch）、深度优先搜索算法(DepthFirstSearch)和并查集（Union-FindSet）这三种方法。为了更好、更生动的表示这些算法的运算过程，在这里如果使用动态显示算法的求解过程将会是最好的选择。对于不同的算法其求解最小生成树时运算的效率是不同的，因此还需要对各种算法时间复杂度进行分析和比较，从而更加深入的理解算法，从而方便我们在不同的场合采用不同的实现算法。1.1.3方案选择通过对题目的分析，对于如何将广度优先搜索算法（BreadthFirstSearch）、深度优先搜1111s1s3325465652441731712索算法(DepthFirstSearch)和并查集（Union-FindSet）这三种方法运用到对边通分量进行查询和合并中有不同的结合方法。在这里我选择了将这三种搜索算法融合到Kruskal算法，因为我觉得在Kruskal算法对边通分量进行查询和合并中使用这三种方法更合理且更容易实现，因此也实现了将这三种搜索算法融合到Kruskal算法从而实现对图的最小生成树的查找。对于运用图形学的知识实现算法的动态运行效果。可以知道使用MFC通过单文档画图来实现算法动态显示运行效果或者使用对话框来实现算法动态显示运行效果，为了方便起见，我选择的是通过MFC建立单文档来实现这一效果。1.1.4开发平台使用的系统是Windows07，开发工具VC++6.01.2系统总体设计由于这是对图进行相关的操作，因此涉及图的存储问题，在这里使用的是邻接矩阵这一数据结构来实现图的存储。在对图进行相关操作寻找最小生成树时，得到的生成树中的边采用的是结构体的存储方式，在实现的过程中相关变量和数据的存储也主要通过数组、结构体来实现了。在深度优先搜索算法（BreadthFirstSearch）中使用了栈这一数据结构来实现边的连通分量的查询，对广度优先搜索算法(DepthFirstSearch)的实现使用了队列这一数据结构，这里的队列和栈都是通过编程实现。这里主要分为六个模块，即prime算法模块、kruskal算法模块、用并查集实现kruskal算法的模块、kruskal算法和深度优先搜索算法结合的模块、kruskal算法和广度优先搜索算法结合的模块以及画图操作的相关模块。设计与实现中由于所体现的重点不同，因此下面的说明主要围绕着此题的重点，即最小生成树的生成过程。对于最小生成树生成过程中边相关变量的存储均是通过定义一个边（edge）的结构体变量进行存储的，而关于点的存储则是通过定义数组进行相应的存储，由于不同的实现方法采用的初始值不一样，因此使用的数组会有所不同。对于算法运行时的动态显示运行过程这一要求主要通过将相关的画圆、画线等相关画图的操作扦插到相关的算法中，在算法的运行过程中再通过对相关条件的判断从而决定是否执行画圆、画线等操作。在这些算法运行过程中实现的画图操作主要通过调用一个公用的函数进行画图的相关操作。二．详细设计与实现2.1Prime算法动态演示模块2.1.1基本思想Prime算法的基本思想是以图中的某一个顶点作为起始顶点，然后从起始顶点出发不断的从还没有遍历到的顶点中选择与已经遍历到的顶点存在之间权值最小边的顶点，并将新遍历的点不断的添加到已经遍历的顶点集合中。通过这样的一个遍历过程与画图的相关操作结合来实现最小生成树生成过程的动态演示。对于无向连通图G（V,E），在prime算法中，将图G顶点集合分为两个集合V1（G）和V2（G），V1（G）用来存储当前已经遍历到的顶点，即最小生成树中的顶点V(MST)，V2（G）3用来存储还没有遍历到的顶点。对于已经选择的顶点之间的边存储在最小生成树的边的集合中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算法的动态演示，主要是关乎两个函数的实现一个是画图函数的实现，另外一个就是如何判断何时进行画图操作并进行相关操作的画