最小生成树求解课程设计.docVIP

合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程 数据结构与算法 课程设计名称 最小生成树求解 学生姓名 学号 专业班级 指导教师 2010 年 6 月 题目：最小生成树求解 设计程序完成如下功能：对于任意给定的的网和起点，用PRIM算法的基本思想求解出所有的最小生成树。 一、问题分析和任务定义 此程序需要完成如下要求：对于任意给定的网和起点，用普利姆算法的基本思想求解出最小生成树，并最终输出得到的所有的最小生成树。 实现该程序功能需要解决以下几个问题： （1）如何选择存储结构去建立一个带权无向图。 （2）在所选存储结构下怎样输出所建立的带权无向图。 （3）如何实现PRIM算法的功能。 （4）如何以各顶点为起点找到所有的最小生成树。 （5）怎样输出得到的所有的最小生成树。 解决问题的关键在于如何实现普利姆算法，实现的过程中如何得到所有的最小生成树以及怎样将其进行输出，所以我在设计程序的过程中经过了深入的思考以及多次的修改程序。 首先对问题进行概要分析： （1）这个问题需要通过普利姆算法的基本思想实现程序所要求的功能。 （2）问题的输入数据的类型为：输入带权网的顶点数和边数被定义为整型数据类型；输入每一个顶点的信息，也设为整型数据类型；输入每一条边的信息，即边的两个顶点以及权值，也是十进制整数类型。 （3）问题的输出数据的格式为：输出的是以邻接矩阵存储结构下的方阵，以及从不同顶点开始生成的最小生成树，输出得到最小生成树的各边以及对应权值都是整型数据类型。 （4）设计测试的实例： 第一个测试实例图如下： 在这种情况下，测试的输出结果如果正确则应该如下： 邻接矩阵为： 从顶点1开始，得到的最小生成树为： 根据预测结果，由图1得到的最小生成树均如图2所示，所以不依次列出图形。 第二个测试实例图如下： 在这种情况下，测试的输出结果如果正确则应该如下： 邻接矩阵为： 从顶点1开始，得到的最小生成树为： 从图3的其他顶点遍历得到的最小生成树图形和图4一样，所以，也不再一一列出，但是，得出的序列应不同。 二、数据结构的选择和概要设计 1．数据结构的选择 本题中用到的数据结构有图和数组。 由于本题主要是对于一个无向网（带权图）进行分析求解，所以必须有图的数据结构。 带权图的存储形式：要实现对于任意给定网和起点，运用PRIM基本算法思想求解所有的最小生成树的运算，我们首先要明确我们所运用的数据结构。这里我选用图的邻接矩阵的存储方式来存储带权无向图。建图时采用邻接矩阵的结构，定义邻接矩阵结构类型时用到一维数组和二维数组，分别存储顶点的信息和边的权值。如果采用邻接表作为图的存储结构，则不能对边的权值进行存储和运算。因为该算法对图中的边的权值频繁的比较，所以采用邻接矩阵方便比较,并在其基础上实现带权网络的建立以及输出显示。 2. 概要设计 针对问题分析中提到的问题，分别设计算法思想。 关于创建无向网的算法，重点是生成邻接矩阵。首先需要确定矩阵和图的结构类型和其中包括的分量。对于一个确定的图，可以用一个一维数组去存储顶点的信息。再将顶点以矩阵的形式存储。图的顶点的个数形成矩阵的行数和列数，而各顶点邻接的顶点与该顶点之间的边的权值则作为矩阵中的元素，如果两个顶点之间不连通，则对应位置上的值为0。这样，就可以用矩阵表示出这个图。所以，定义一个二维数组表示一个矩阵，图的顶点的个数则是数组的下标。而无向图的邻接矩阵是对称的，所以，在存储时，只需要存储上三角（或下三角）的元素。而另外一部分元素，则可通过互换二维数组的下标来存储。 关于PRIM算法求解最小生成树的算法基本思想： 最小生成树（MST）U为空集。 （2）任意选取一个顶点v加入U。 （3）选取一条权值最小的边（u，v）u∈U，v∈（V-U）v加入到U中。 （4）重复步骤（3），直到所有顶点均加入到U中即构成一棵最小生成树。 具体的过程就是：首先任意选择一个顶点，找到与它相关的所有的边，比较这些边上的权值大小，将权值最小的那条边的信息赋给一个自定义的变量，然后将选中的这条边的另外一个顶点和该顶点一起放在一个集合中，再次比较和这两个顶点相连通的其他的所有边，同样将权值最小的那条边的信息赋给同样的变量。然后，就通过循环，不断地加点，逐步的将各个顶点全部遍历，最后形成了由选中的所有的最小权值的边构成的要求解的最小生成树。而输出最小生成树的时候，则将这些边的信息依次输出。为了实现这一过程，需要设一个辅助数组，来存储所有选中的最小权值边的信息，即上述的变量。这样，便于区别遍历过和未遍历的顶点，而且，在输出最小生成树信息时，可以很方便的输出。 输出所有的最小生成树则是通过循环实现的，循环范围是图的顶点数。每次执行求解最小生成树的