最小生成树求解课程设计

《最小生成树求解课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称最小生成树求解学生姓名学号专业班级指导教师2010年6月题目：最小生成树求解设计程序完成如下功能：对于任意给定的的网和起点，用PRIM算法的基本思想求解出所有的最小生成树。一、问题分析和任务定义此程序需要完成如下要求：对于任意给定的网和起点，用普利姆算法的基本思想求解出最小生成树，并最终输出得到的所有的最小生成树。实现该程序功能需要解决以下几个问题：（1）如何选择存储结构去建立一个带权无向图。（2）在所选存储结构下怎样输出所建立的带权无向图。（3）如何实现PRIM算法的功能。（4）如何以各顶点为起

2、点找到所有的最小生成树。（5）怎样输出得到的所有的最小生成树。解决问题的关键在于如何实现普利姆算法，实现的过程中如何得到所有的最小生成树以及怎样将其进行输出，所以我在设计程序的过程中经过了深入的思考以及多次的修改程序。首先对问题进行概要分析：（1）这个问题需要通过普利姆算法的基本思想实现程序所要求的功能。（2）问题的输入数据的类型为：输入带权网的顶点数和边数被定义为整型数据类型；输入每一个顶点的信息，也设为整型数据类型；输入每一条边的信息，即边的两个顶点以及权值，也是十进制整数类型。（3）问题的输出数据的格式为：输出的是以邻接矩阵存储结构下的方阵，以及从不同顶点开始生成的最小生成树，输出得到最

3、小生成树的各边以及对应权值都是整型数据类型。（4）设计测试的实例：第一个测试实例图如下：12344263图1第一个测试实例在这种情况下，测试的输出结果如果正确则应该如下：邻接矩阵为：0342300040062060图2图1的邻接矩阵从顶点1开始，得到的最小生成树为：1234423图3图1从顶点1遍历得到的最小生成树根据预测结果，由图1得到的最小生成树均如图2所示，所以不依次列出图形。第二个测试实例图如下：9123453254768图4第二个测试实例在这种情况下，测试的输出结果如果正确则应该如下：邻接矩阵为：0320530049200860480759670图5图4的邻接矩阵从顶点1开始，得到的

4、最小生成树为：123453254图6图4从顶点1开始得到的最小生成树从图3的其他顶点遍历得到的最小生成树图形和图4一样，所以，也不再一一列出，但是，得出的序列应不同。二、数据结构的选择和概要设计1．数据结构的选择本题中用到的数据结构有图和数组。由于本题主要是对于一个无向网（带权图）进行分析求解，所以必须有图的数据结构。带权图的存储形式：要实现对于任意给定网和起点，运用PRIM基本算法思想求解所有的最小生成树的运算，我们首先要明确我们所运用的数据结构。这里我选用图的邻接矩阵的存储方式来存储带权无向图。建图时采用邻接矩阵的结构，定义邻接矩阵结构类型时用到一维数组和二维数组，分别存储顶点的信息和边的

5、权值。如果采用邻接表作为图的存储结构，则不能对边的权值进行存储和运算。因为该算法对图中的边的权值频繁的比较，所以采用邻接矩阵方便比较,并在其基础上实现带权网络的建立以及输出显示。2.概要设计针对问题分析中提到的问题，分别设计算法思想。关于创建无向网的算法，重点是生成邻接矩阵。首先需要确定矩阵和图的结构类型和其中包括的分量。对于一个确定的图，可以用一个一维数组去存储顶点的信息。再将顶点以矩阵的形式存储。图的顶点的个数形成矩阵的行数和列数，而各顶点邻接的顶点与该顶点之间的边的权值则作为矩阵中的元素，如果两个顶点之间不连通，则对应位置上的值为0。这样，就可以用矩阵表示出这个图。所以，定义一个二维数组

6、表示一个矩阵，图的顶点的个数则是数组的下标。而无向图的邻接矩阵是对称的，所以，在存储时，只需要存储上三角（或下三角）的元素。而另外一部分元素，则可通过互换二维数组的下标来存储。关于PRIM算法求解最小生成树的算法基本思想：最小生成树（MST）是指在所有生成树中，边上权值之和最小的生成树。另外，最小生成树也可能是多个，而且它们之间的权值之和相等。普利姆算法则是按照将顶点逐个连通的步骤，把顶点加入到已连通顶点集合U中，最后使U成为最小生成树。（1）初始化顶点集合U为空集。（2）任意选取一个顶点v加入U。（3）选取一条权值最小的边（u，v），其中u∈U，v∈（V-U），将该边加入到生成树，v加入到U

7、中。（4）重复步骤（3），直到所有顶点均加入到U中即构成一棵最小生成树。具体的过程就是：首先任意选择一个顶点，找到与它相关的所有的边，比较这些边上的权值大小，将权值最小的那条边的信息赋给一个自定义的变量，然后将选中的这条边的另外一个顶点和该顶点一起放在一个集合中，再次比较和这两个顶点相连通的其他的所有边，同样将权值最小的那条边的信息赋给同样的变量。然后，就通过循环，不断地加点，逐步的将各个顶点全部