贪心求解最小生成树.ppt

算法分析与设计,贪心算法求解最小生成树问题学号：姓名：代课老师：,最小生成树,问题描述：考虑无向图G=（V，E），假定该图代表不同城市间的通信网络情况，图的顶点表示城市，边（v,w）的权值cvw表示建立城市v和w之间的通信线路所需的费用，这样得到一个无向连通带权图。在实际问题中，人们往往希望在该结构上选择一组通信线路，它们连接所有的城市并且是最经济的方案。问题分析：该问题相当于求解连通带权图的具有最小权值的生成树，我们称之为最小生成树问题。,相关概念,最小生成树：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。最小生成树的性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。,贪心算法的基本要素,贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本要素是贪心选择性质和最优子结构性质。,证明最小生成树问题满足最优子结构性质：,假设G的任何一棵最小生成树都不含边(u,v)。将边(u,v)添加到G的一棵最小生成树T上，将产生含有边(u,v)的圈，并且在这个圈上有一条不同于(u,v)的边(u,v)，使得uU,vV-U,如图所示：将边(u,v)删去，得到G的另一棵生成树T。由于cuvcuv,所以T的耗费T的耗费。意识T是一棵含有边(u,v)的最小生成树，这与假设矛盾。,U,V-U,u,u,v,v,Prime算法,基本思想：设G=（V，E）是连通带权图，V=1,2，n。首先设S=1，然后，只要S是V的真子集，就做如下的贪心选择：选取满足条件iS,jV-S，且cij最小的边，并将顶点j添加到S中。这一过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。基础：G的最小生成树的边数是顶点数-1。,Prime算法选边过程：,算法相关说明,cij:边(i,j)的权S：标记已经加入到最小生成树的顶点closestj:对于每一个jV-S是j在S中的邻接顶点，它与j在S中的其他邻接顶点k相比较有：cjclosestjcjklowcostj:即cjclosestjPrime算法：先找出V-S中使lowcost值最小的顶点j，然后根据书中closest选取边(j,closestj),最后将j添加到中，并对closest和lowcost做必要的修改。时间复杂度：，是顶点个数,publicclassPrimpublicstaticvoidprim(intnum,floatweight)/num为顶点数，weight为权floatlowcost=newfloatnum+1;/到新集合的最小权intclosest=newintnum+1;/代表与s集合相连的最小权边的点booleans=newbooleannum+1;/si=true代表i点在s集合中s1=true;/将第一个点放入s集合for(inti=2;i=num;i+)/初始化辅助数组lowcosti=weight1i;closesti=1;si=false;for(inti=1;inum;i+)System.out.println(第+i+次：);floatmin=Float.MAX_VALUE;intj=1;for(intk=2;k=num;k+)/根据最小权加入新点if(lowcostkmin),运行结果：,Kruskal算法,基本思想：将的个顶点看成个孤立的连通分支，将所有的边按权从小到大排序,依边权递增的顺序查看每一条边。连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支。继续查看第k+1条边：如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止,Kruskal算法选边过程：,6,假设无向连通带权图顶点数为n，边数为e，经典Prime算法的时间复杂度是