贪心法求最小生成树算法

贪心策略求最小生成树问题设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树(MinimalSpanningTrees)。最小生成树问题至少有两种合理的贪心策略：(1)最近顶点策略：任选一个顶点，并以此建立起生成树，每一步的贪心选择是简单地把不在生成树中的最近顶点添加到生成树中。Prim算法就应用了这个贪心策略,它使生成树以一种自然的方式生长，即从任意顶点开始，每一步为这棵树添加一个分枝，直到生成树中包含全部顶点。1717(e)U={A,F,C,D,E}(e)U={A,F,C,D,E}cost={(E,B)12}(f)U={A,F,C,D,E,B}cost={(A,B)34,(F,E)26}设图G中顶点的编号为0〜n-1.Prim算法如下：算法7.4——Prim算法初始化两个辅助数组lowcost和adjvex；U={u0};输出顶点u0; //将顶点u0加入生成树中重复执行下列操作n-1次3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；输出顶点k和对应的权值；U=U+{k}；调整数组lowcost和adjvex；上述伪代码中，数组closest[j]是j(jlV-S)在S中的领接顶点，它与j在S中的其它顶点相比较有c[j][cloest[j]]<=c[j][k]olowest[j啲值就是c[j][cloest[j]]。在算法执行过程中，先找出V-S中是lowest值最小的顶点j,然后根据数组closest选取边(j,cloest[j])，最后将j添加到S

中，并对closest和lowest作必要的修改。程序运行结果为：连通带权图的矩阵为，599999999999939999599999999999939999564999999992999999996包999955999999995=99936.99999994269999Pf5算法最小生成权寸注边複序如卫fi63623请按任意键继续.利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。设连通网中有n个顶点，则第一个进行初始化的循环语句需要执行n-1次，第二个循环共执行n-1次，内嵌两个循环，其一是在长度为n的数组中求最小值，需要执行n-1次，其二是调整辅助数组，需要执行n-1次，所以，Prim算法的时间复杂度为O(n2)。2)最短边策略：设G=(V，E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选取最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。Kruskal算法就应用了这个贪心策略，它使生成树以一种随意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，到最后合并成一棵树。实现算法Kruskal需要准备两个数据结构：(1)最小堆MinHeap,按权的递增顺序查看的边的序列可以看做是一个优先队列，它的优先级为边权；2)并查集UnionFind,主要包括Union(a,b)和Find(v)两个基本运算：Union(a,b)将两个连通分支a和b连接起来，所得的结果为A或B；Find(v)返货U总包含顶点v的连通分支的名字。这个运算用来确定某条边的两个端点所属的连通分支。(d)(f)(e)(f)算法7.5——Kruskal算法初始化：U=v； TE={}；循环直到T中的连通分量个数为12.1在E中寻找最短边(u,v);2.2如果顶点u、v位于T的两个不同连通分量，则将边(u,v)并入TE；将这两个连通分量合为一个；2.3E=E-{(u，v)}；当图的边数为e时,Kruskal算法所需的计算时间是〜。当匚_八一〔时,Kruskal算法比Prim算法差，但当= U时，Kruskal算法却比Prim算法好得多。程序运行结果为：狂通带权图所有边的两端顶詆叔分别为:u：l,weight：6□.u：2Li:1,weight:l,u：3u：l,weight：5,u：411=2,weight：5：3u：2,ueight:3,u：5u：3,weight：5.s4u：3,weight：4,u：6it：3,weight:6,u汚u：4,weight：2小北li：5,weight:6j-u：6Kruskal算法最小生成树选择结果为；u：1,weight：1Au：3it：4,weight:2,u:Em2,weight：3：5it：3,weight:4,u：6u：2,weight：5,u：3请按任意键继续•••■Kruskal算法为了提高每次贪心选择时查找最短边的效率，可以先将图G中的边按代价从小到大排序，则这个操作的时间复杂度为O(elog2e),其中e为无向连通网中边的个数。对于两个顶点是否属于同一个连通分量，可以用并查集的操作将其时间性能提高到O(n),所以,Kruskal算法的时间性能是O(elog2e)。实验小结：通过这次实验，我们深刻了解到贪心法的概念。贪心法(greedymethod)是把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个扩展,直到获得问题的完整解。贪心法的典型应用是求解最优化问