贪心算法 最小生成树

1、贪心算法 最小生成树 课程设计说明书(论文)用纸 摘 要 络的最小生成树在实际中有广泛的应用，例如，络g表示n各城市之间的通信线路线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该络的最小生成树达到求解通信线路或总代价最小的最佳方案。本课程设计采用贪心算法中prim算法解决最小生成树问题，贪心算法包括两个基本要素：最优子结构性质和贪心选择利性质，贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。通过分析用贪心算法解决最小生成树问题能得到问题的最优解。 根据算法的设计结果，采用c+语言实现算法，通过测试分析，程序

2、运行结果正确，运行效率较高。 关键词：最小生成树， 贪心算法 i 课程设计说明书(论文)用纸 目 录 1 问题描述. 1 2 问题分析. 2 3 建立数学模型. 3 4 算法设计. 5 5 算法实现. 6 6 测试分析. 12 结 论. 13 参考文献. 14 ii 课程设计说明书(论文)用纸 1 问题描述 设图g=(v，e)是一简单连通图，|v|=n，|e|=m，每条边ei都给以权wi，wi假定是边ei的长度（其他的也可以），i=1，2，3，?，m。求图g的总长度最短的树。首先置s=1，然后，只要s是v的真子集，就作如下的贪心选择：选取满足条件i?s，j?v-s，且cij最小的边，将顶点j添

3、加到s中。这个过程一直进行到s=v时为止。在这个过程中选取到的所有边恰好构成g的一棵最小生成树。 第1页 共14页 课程设计说明书(论文)用纸 2 问题分析 首先置s=1，然后，只要s是v的真子集，就作如下的贪心选择：选取满足条件i?s，j?v-s，且cij最小的边，将顶点j添加到s中。这个过程一直进行到s=v时为止。在这个过程中选取到的所有边恰好构成g的一棵最小生成树。 该算法的特点是当前形成的集合t始终是一棵树。将t中u和te分别看作红点和红边集，v-u看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进t中。mst性质保证了此边是安全的。t从任意的根r开始，并逐渐生长直

4、至u=v，即t包含了c中所有的顶点为止。mst性质确保此时的t是g的一棵mst。因为每次添加的边是使树中的权尽可能小，因此这是一种“贪心”的策略。 该算法的时间复杂度为o(n2)。与图中边数无关，该算法适合于稠密图。 基本思想：首先将g的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支t1和t2中的顶点时，就用边(v,w)将t1和t2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再

5、查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是g的一棵最小生成树。 当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要o(e)时间，在上述算法的while循环中，deletemin运算需要o(loge)时间，因此关于优先队列所作运算的时间为o(eloge)。实现unionfind所需的时间为o(eloge)或o(elog*e)。所以kruskal算法所需的计算时间为o(eloge)。 当e=(n2)时，kruskal算法比prim算法差，但当e=o(n2)时，kruskal算法却比prim算法好得多。kruskal算法的时间主要取决于边数。它较

6、适合于稀疏图。 第2页 共14页 课程设计说明书(论文)用纸 3 建立数学模型 1 . 在编译时，出现有些库函数没有定义和警告错误； 解决方法：需要在程序首部加入以下包含文件：#include、 #include、#include、#include ；出现的警告错误是由于定义一指针变量时，需用库函数malloc（）为其分配内存空间 2 . 在创建无向函数creat()中，当输入的顶点个数解决方法：通过在函数首部定义一标记变量flag，将其初始化为0，当输入的顶点个数v1v2weight; ” 输入边所关联的两个顶点和权值； 3 . 在函数minium()中，当用语句“min=close0.lowcost”初始化min时，会导致结果出现错误； 解决方法：用语句“min=infinit;”可以将其置为； 4. 在普里姆算法函数prim()，如何将最小生成树中的顶点序列显示出来； 解决方法：首先，定义adjmatrix结构体类型的指针变量*p，并通过语 句“p-vexsn+=u;”将起点存入顶点向量表中，然后在for循环体中用语句“p-vexsn+=v0;”将每条边的终点依次放入顶点向量表中，最后向量表中的数据就是最小生成树中的顶点序列，通过fou循环将其输出； 5. 在输出邻接矩阵函数display()中，如何将矩阵中值为infinit的元素在屏幕上用