最小生成树求解课程设计报告

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

1、数据结构与算法课程设计报告合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称最小生成树求解学生姓名谷敏敏学号0804012023专业班级08计科(2)班指导教师王昆仑、张贯虹2010年6月-18-数据结构与算法课程设计报告1课程设计题目对任意给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树。2问题分析和任务定义本课程设计重在使用prim算法实现任意给定的网和起点的图的所有最小生成树的求解，实现本课程设计的关键即是能够掌握prim算法的思想，并能够灵活使用。首先我

2、们必须对prim算法有个清晰地认识，prim算法是普利姆（Prime）于1957年提出了一种构造最小生成树的算法，算法的主要思想如下：按照将顶点逐个连通的步骤，把顶点加入到已经连通的顶点集合U中，最后使得U成为最小生成树。PRIM思路：1）初始化顶点集合U为空集。2）任意选取一个顶点v加入U。3）选取一条权值最小的边（u,v），其中u∈U，v∈（V-U），将该边假如到生成树，v加入到U中。4）重复步骤3），直到所有顶点均加入到U中构成一颗最小生成树。为了实现这一算法需要附设一个辅助数组closedge[v]用来存储从U到V

3、-U之间具有最小代价的边。对于每个顶点v∈（V-U），在closedge，树组中都存在一个分量closedge[v]，它有两个域组成。其中一个是权值，即：closedge[v].lowcost=MIN{cost（u,v）

4、u∈U}，另外一个是顶点域vexs，存储依附于该边在U中的顶点。其次，针对本课程设计的题目要求，我们需要考虑到五个问题：Ø如何选择、设计一个合适的算法来建立图，用以实现接下来的操作。Ø如何正确的在本实验中使用prim算法。Ø对于本课程设计中的需要，求出对于给定任意给定的网和结点，得出所有的最小生成树，关键

5、在于需要求出所有的最小生成树，需要灵活使用prim算法实现。Ø对于一些细节也是需要考虑斟酌的，比如，当所输入的顶点不存在时，需要一个示语句警示，并能够重新输入。Ø当算法设计完成后，还需对于整个运行程序的运行界面，提示语句以及如何完美、清楚的输出各个最小生成树设计一番。最后，在课程设计过程中，自己需要做好充足的准备工作，吃透课本中关于prim算法的解释说明，同时把握好时间，掌握整个课程设计的进度，做好整体规划，保证本次课程设计可以及时的、成功的设计出来。3数据结构的选择和概要设计Ø对于本次设计，在prim算法中使用的图均为无

6、向图，对于各顶点之间的权值以及连通关系是采用邻接矩阵来实现的。同时在prim算法中采用了辅助数组closedge[v]，主要用来存储到顶点的最小边权值。建立图的数据结构类型如下：typedefstruct{intvexs[MAX];//顶点信息集合intarcs[MAX][MAX];//各边的权值-18-数据结构与算法课程设计报告intvexnum;//顶点数intarcnum;//边数}MGraph;//图类型建立辅助数组结构类型如下：structclosed{intadjvex;//依附于最小权值边在顶点集合U中的顶点

7、intlowcost;//存储最小边的权值};closedclosedge[MAX];1.1.1整个算法概要设计主要在于图的初始化，以及如何求出所有最小生成树。下面我们可以通过相应的流程图来清楚的理解。1.1.1.1刚开始时初始化各顶点的顶点域、权值域赋值的算法流程:开始把1赋给j判断j是否等于输入的顶点数值j不等于I把I的值赋给j的顶点域里；把邻接矩阵中处于[j][I]位置的值赋给j的权值域中。j等于I把j+1赋给j判断j是否小于等于图的顶点数小于等于大于把0赋给顶点I的权值域-18-数据结构与算法课程设计报告Ø.求出最

8、小代价的边的算法流程:把1赋给j把1赋给i把邻接矩阵中处于[1][i]位置的值赋给i的权值域中;把1赋给i的顶点域中把i+1赋给i判断i是否小于图的顶点数小于大于等于把0赋给1的顶点域中，把1赋给j此时j的权值域是否小于minj的顶点域是否等于0j的顶点域是否等于0把1赋给j把100赋给min,把i的值赋给k.把1赋给i-18-数据结构与算法课程设计报告有一个条件不满足都是肯定的回答把顶点j里的权值域中的值赋给最小值min，把j赋给k把j+1赋给j判断j是否小于等于图的顶点数是否用两个顶点的集合输出边。将顶点k加入到U中，

9、表示k顶点已拿走了，把0赋给k的权值域中，这是标志性的赋值。对于上述流程图可简单解释如下，首先通过对其它顶点依次判断，找出相连的顶点，然后得到顶点序号，再通过for循环，进行循环判断，找出边权值最小的，并赋值进入closedge[]中。-18-数据结构与算法课程设计报告Ø重新调整各顶点中的顶点域和权值域