最小生成树问题ppt课件

1、边的权边的权:G=(V,E):G=(V,E)对每边对每边eiEeiE规定一个非负的实数规定一个非负的实数w(ei)w(ei)叫叫“权权”；带权图带权图: :每边都有权的图叫赋权图或带权图；每边都有权的图叫赋权图或带权图；树树: :其特点之一是边数比顶点数少一；其特点之一是边数比顶点数少一；图图G G的支撑树的支撑树T:E(T)T:E(T)E(G),V(T)=V(G),E(G),V(T)=V(G),即由即由G G找找T T，顶点一个不能少，顶点一个不能少，边可能删去几条，但边可能删去几条，但T T必须是树必须是树 当然如当然如G G不是连通图，则没有支撑树不是连通图，则没有支撑树 。最小树最小树

2、: :赋权的连通图赋权的连通图G G的众多支撑树中必至少有一，其各边权之和为的众多支撑树中必至少有一，其各边权之和为最小的，它就叫最小的，它就叫G G的一棵最小支撑树或最小生成树；简称最小树或最短的一棵最小支撑树或最小生成树；简称最小树或最短树树 管线铺设管线铺设 。最小树的存在性：赋权的连通图最小树的存在性：赋权的连通图G =(V,E),G =(V,E),记记m=|E|, n=|V|,m=|E|, n=|V|,支撑树支撑树T T的的边数边数|E(T)|=n-1,E(T)|E(T)|=n-1,E(T)必为必为V V的的n-1n-1元子集，显然这种子集合最多元子集，显然这种子集合最多 个，所以支

3、撑树是有限的，其权组成有限集，必有最小的个，所以支撑树是有限的，其权组成有限集，必有最小的 但可能不唯但可能不唯一一 。 1nmC赋权的连通图赋权的连通图G=(V,E)G=(V,E)中中m=|E|,n=|V|, m=|E|,n=|V|, S1:S1:对对E E中各边的权排序，设中各边的权排序，设w1w2wm,wi=w(ei)w1w2wm,wi=w(ei)S2:S2:初始化：初始化：w0,T,k1,t0w0,T,k1,t0S3:S3:若若t=n-1t=n-1则转则转S6S6，否则转，否则转S4S4S4:S4:若若TekTek有圈则有圈则kk+1kk+1转转S4S4，否则转否则转S5S5S5: T

4、Tek,ww+wk,S5: TTek,ww+wk, tt+1, kk+1, tt+1, kk+1,转转S3S3S6:S6:输出输出T T及及w w，终了。，终了。T T为最小树，为最小树，w w为为T T的权。这个算的权。这个算法叫法叫KruskalKruskal算法算法( (避圈法避圈法) )TTekt=n-1?kk+1NY输出输出T,wENDSTARTE的权排序的权排序w1w2wmw0,T,k1,t0T成圈?YNTT+ ek, ww+wk, tt+1,kk+1用用KruskalKruskal算法算法( (避圈法避圈法) )求赋权连通图求赋权连通图G G的最小树的最小树V1V2V3V5V4V

5、6V723798105612445611723644565最小树的权为最小树的权为24，最小树为，最小树为T=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4KruskalKruskal算法的算法的“主要工作如认为是主要工作如认为是S1:S1:对对m m条边的边长排序，条边的边长排序，m m个元素排序较好的算法是基于分治个元素排序较好的算法是基于分治策略的快速排序策略的快速排序(Quick Sorting)(Quick Sorting)，其时间复杂性是，其时间复杂性是O(mO(mm)m)。快速排序算法：快速排序算法：找一个数如第一个找一个数如第一个k k，待排序的数可以分为大于，待排

6、序的数可以分为大于k k的和小于的和小于k k的两部分，分别对这两部分继续用快速排序的两部分，分别对这两部分继续用快速排序 递归递归 ，最，最后合并联接就可以了。后合并联接就可以了。阐明：阐明：“是否成圈的判断事实上不比边长排序来得容易，尤其是否成圈的判断事实上不比边长排序来得容易，尤其是用计算机程序实现时。要让程序读懂是用计算机程序实现时。要让程序读懂“图图”，程序如何，程序如何判断是否成判断是否成“圈圈”？谈何容易，时间、空间复杂性绝不应？谈何容易，时间、空间复杂性绝不应小看小看KruskalKruskal法盯住边法盯住边, ,而而PrimPrim法更注意顶点法更注意顶点: :从任一顶点开始都可以从任一顶点开始都可以, ,逐个把最近的顶点找进来逐个把最近的顶点找进来( (找过的不找找过的不找, ,就不会成圈就不会成圈) )。算法如下算法如下: :S1:Tv1, SVv1, w0S1:Tv1, SVv1, w0S2:S2:若若S=S=转转S5,S5,否则转否则转S3S3S3:S3:S4:TTvk,SSvk,ww+w(vlvk),S4:TTvk,SSvk,ww+w(vlvk),转转S2S2S5:S5:输出输出T T及及w,w,停顿停顿. .)vv(w)vv(wmin:kljiTvSvji设用用PrimPrim算法算法( (就近法就近法) )求赋权连通图求赋权连