最小生成树问题.ppt

2017-5-3最小生成树问题最小生成树问题 2017-5-3 赋权连通图的最小支撑树赋权连通图的最小支撑树?边的权:G=(V,E) 对每边 e i∈E规定一个非负的实数 w(e i)叫“权”; ?带权图:每边都有权的图叫赋权图或带权图; ?树:其特点之一是边数比顶点数少一; ?图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 元子集,显然这种子集合最多个,所以支撑树是有限的,其权组成有限集,必有最小的[但可能不唯一]。 1?nmC 2017-5-3 求最小树的求最小树的 Kruskal Kruskal 算法算法赋权的连通图 G=(V,E) 中 m=|E|,n=|V|, S1: 对E中各边的权排序,设 w 1≤w 2≤…≤ w m,w i=w(e i) S2: 初始化:w←0,T ←φ,k←1,t ←0S3: 若t=n-1 则转 S6,否则转 S4 S4: 若T∪{e k}有圈则 k←k+1 转S4, 否则转 S5 S5: T ←T∪{e k},w ←w+w k, t ←t+1, k ←k+1, 转S3 S6: 输出 T及w,结束。 T为最小树, w为T的权。这个算法叫 Kruskal 算法(避圈法)T’←← T∪{e k} t=n-1? k← k+1 N Y输出 T,w END START E的权排序 w 1≤w 2≤…≤w m w←0,T ←φ,k←1,t ←0T’成圈?Y NT← T+ {e k }, w← w+w k, t← t+1,k ← k+1 2017-5-3 用用Kruskal Kruskal 算法求最小树算法求最小树用Kruskal 算法(避圈法)求赋权连通图 G的最小树 V 1 V 2V 3V 5V 4 V 6V 7 237 9810 56 12 44 5611 7 236 44 56 5∴最小树的权为 24,最小树为 T={v 1v 2,v 1v 3,v 2v 5,v 5v 6,v 6v 7,v 6v 4} 2017-5-3 避圈法求最小树的分析避圈法求最小树的分析 Kruskal 算法的“主要”工作如认为是[S1:] 对m条边的边长排序, m个元素排序较好的算法是基于分治分治策略策略的快速排序快速排序(Quick Sorting) ,其时间复杂性是 O(m ㏒ m)。快速排序快速排序算法: 找一个数如第一个 k,待排序的数可以分为大于 k的和小于 k的两部分,分别对这两部分继续用快速排序[递归],最后合并联接就可以了。说明说明: “是否成圈”的判断事实上不比边长排序来得容易,尤其是用计算机程序实现时。要让程序读懂“图”,程序如何判断是否成“圈”?谈何容易,时间、空间复杂性绝不应小看 2017-5-3 Prim Prim 法求最小支撑树法求最小支撑树?Kruskal 法盯住边,而Prim 法更注意顶点: ?从任一顶