文档介绍：最小生成树问题*赋权连通图的最小支撑树边的权:G=(V,E)对每边ei∈E规定一个非负的实数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元子集,显然这种子集合最多个,所以支撑树是有限的,其权组成有限集,必有最小的[但可能不唯一]。Date求最小树的Kruskal算法赋权的连通图G=(V,E)中m=|E|,n=|V|,S1:对E中各边的权排序,设w1≤w2≤…≤wm,wi=w(ei)S2:初始化:w←0,T←φ,k←1,t←0S3:若t=n-1则转S6,否则转S4S4:若T∪{ek}有圈则k←k+1转S4,否则转S5S5:T←T∪{ek},w←w+wk,t←t+1,k←k+1,转S3S6:输出T及w,结束。T为最小树,w为T的权。这个算法叫Kruskal算法(避圈法)T’←T∪{ek}t=n-1?k←k+1NY输出T,wENDSTARTE的权排序w1≤w2≤…≤wmw←0,T←φ,k←1,t←0T’成圈?YNT←T+{ek},w←w+wk,t←t+1,k←k+1Date用Kruskal算法求最小树用Kruskal算法(避圈法)求赋权连通图G的最小树V1V2V3V5V4V6V7237981056124456**********∴最小树的权为24,最小树为T={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}Date避圈法求最小树的分析Kruskal算法的“主要”工作如认为是[S1:] 对m条边的边长排序,m个元素排序较好的算法是基于分治策略的快速排序(QuickSorting),其时间复杂性是O(m㏒m)。快速排序算法: 找一个数如第一个k,待排序的数可以分为大于k的和小于k的两部分,分别对这两部分继续用快速排序[递归],最后合并联接就可以了。说明: “是否成圈”的判断事实上不比边长排序来得容易,尤其是用计算机程序实现时。要让程序读懂“图”,程序如何判断是否成“圈”?谈何容易,时间、空间复杂性绝不应小看DatePrim法求最小支撑树Kruskal法盯住边,而Prim法更注意顶点:从任一顶点开始都可以,逐个把最近的顶点找进来(找过的不找,就不会成圈)。算法如下:S1:T←{v1},S←V\{v1},w←0S2:若S=φ转S5,否则转S3S3:S4:T←T∪{vk},S←S\{vk},w←w+w(vlvk),转S2S5:输出T及w,(就近法)求赋权连通图G的最小树V1V2V3V5V4V6V7237981056124456117236445∴最小树的权为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