最小生成树问题.ppt

2023/8/23,最小生成树问题,2023/8/23,赋权连通图的最小支撑树,边的权:G=(V,E)对每边eiE规定一个非负的实数w(ei)叫“权”；带权图:每边都有权的图叫赋权图或带权图；树:其特点之一是边数比顶点数少一；图G的支撑树T:E(T)E(G),V(T)=V(G),即由G找T，顶点一个不能少，边可能删去几条，但T必须是树当然如G不是连通图，则没有支撑树。最小树:赋权的连通图G的众多支撑树中必至少有一，其各边权之和为最小的，它就叫G的一棵最小支撑树或最小生成树；简称最小树或最短树管线铺设。最小树的存在性：赋权的连通图G=(V,E),记m=|E|,n=|V|,支撑树T的边数|E(T)|=n-1,E(T)必为V的n-1元子集，显然这种子集合最多 个，所以支撑树是有限的，其权组成有限集，必有最小的但可能不唯一。,2023/8/23,求最小树的Kruskal算法,赋权的连通图G=(V,E)中m=|E|,n=|V|,S1:对E中各边的权排序，设w1w2wm,wi=w(ei)S2:初始化：w0,T,k1,t0S3:若t=n-1则转S6，否则转S4S4:若Tek有圈则kk+1转S4，否则转S5S5:TTek,ww+wk,tt+1,kk+1,转S3S6:输出T及w，结束。T为最小树，w为T的权。这个算法叫Kruskal算法(避圈法),2023/8/23,用Kruskal算法求最小树,用Kruskal算法(避圈法)求赋权连通图G的最小树,最小树的权为24，最小树为T=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,2023/8/23,避圈法求最小树的分析,Kruskal算法的“主要”工作如认为是S1:对m条边的边长排序，m个元素排序较好的算法是基于分治策略的快速排序(Quick Sorting)，其时间复杂性是O(mm)。快速排序算法：找一个数如第一个k，待排序的数可以分为大于k的和小于k的两部分，分别对这两部分继续用快速排序递归，最后合并联接就可以了。说明：“是否成圈”的判断事实上不比边长排序来得容易，尤其是用计算机程序实现时。要让程序读懂“图”，程序如何判断是否成“圈”？谈何容易，时间、空间复杂性绝不应小看,2023/8/23,Prim法求最小支撑树,Kruskal法盯住边,而Prim法更注意顶点:从任一顶点开始都可以,逐个把最近的顶点找进来(找过的不找,就不会成圈)。算法如下:S1:Tv1,SVv1,w0S2:若S=转S5,否则转S3S3:S4:TTvk,SSvk,ww+w(vlvk),转S2S5:输出T及w,停止.,2023/8/23,用Prim算法(就近法)求赋权连通图G的最小树,最小树的权为24，最小树为Tree=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,T=v1,S=v2,v3,v4,v5,v6,v7,T=v1,v2,T=v1,v2,v3,T=v1,v2,v3,v5,T=v1,v2,v3,v5,v6,T=v1,v2,v3,v5,v6,v7,T=v1,v2,v3,v5,v6,v7,v4,