图的最小生成树.pptVIP

第五章 图 5.4 图的最小生成树 难点：生成树概念的理解 重点：普里姆算法、克鲁斯卡尔算法 思考题： 判断下列说法是否正确 （1）图的生成树是唯一的。 （2）在有n个顶点的无向图中，有n-1 条边的图一定是生成树。 深度优先生成树和广度优先生成树P81 根据深度和广度优先有哪些信誉好的足球投注网站法进行遍历就可以得到两种不同的生成树，并分别称为深度优先生成树和广度优先生成树。 5.4.2网络的最小生成树P82 在一个图的每条边或弧上，有时可以标上具有某种含义的数值，这种边或弧上带权的图称为网（Network）。 例如：铺设煤气管道问题（图形结构） 假设要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，管道铺设方案。 在众多可选边中，如何选择n-1条边，使总代价最小？这就是求该网络最小生成树问题。 如何构造图的最小生成树？ Kruskal算法（克鲁斯卡尔）总结 Kruskal算法步骤： 初始时，顶点={图中所有的顶点}，边={φ}。 重复下述操作：在图的边集中按权值自小至大依次选择边，若选取的边使生成树不形成回路，则将该边加入到生成树集合中；依次类推，直到将所有顶点都连通（所有顶点都在同一连通分量上为止），这时产生的具有n-1条边的一棵最小生成树。 【练习】请用kruskal算法找出下图最小生成树。 练习 利用克鲁斯卡尔算法构造最小生成树 算出该最小生成树的代价 练习---利用Prim算法构造最小生成树 算出该最小生成树的代价 利用Prim算法构造最小生成树步骤 利用Prim演算法找最小生成树 以A点为起始点 两种生成树算法比较 克鲁斯卡尔算法 ---------适合求边稀疏的网的最小生成树 普利姆算法 ---------适合求边稠密的网的最小生成树 本节重点 理解生成树概念 重点掌握prim算法和Kruskal算法构造网络的的最小生成树 理解最小生成树的现实意义 【练习1】请对下图的无向带权图： （1） 按普里姆算法求其最小生成树； （2）按克鲁斯卡尔算法求其最小生成树； （3）计算最小生成树的权值； 【练习2】 所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。? 问答题 试着找出下图网G的最小生成树； * * 图的生成树 设无向连通图G=（V，{E}）， 其子图G’=（V，{T}）满足： ① V(G’)=V(G) n个顶点 ② G’是连通的 ③ G’中无回路 则G’是G的生成树 　 判断是否是生成树：具有n个顶点的无向连通图G （１） 必然包括n个顶点 （２） 含n-1条边 （３） 无回路/连通 无向连通图的生成树举例 举例：有如下无向连通图 A C B E D F 图G V0 V2 V3 V7 V4 V6 V1 V5 V1 V0 V3 V7 V4 V2 V5 V6 以V0为起始点,深度优先遍历 深度优先生成树 V7 V3 V4 V2 V1 V6 V5 V0 以V0为起始点,广度优先遍历 广度优先生成树 V0 V1 V3 V2 V4 V5 6 3 6 6 1 6 4 5 2 5 V0 V1 V3 V2 V4 V5 6 6 4 5 5 V0 V1 V3 V2 V4 V5 3 6 1 4 2 V0 V1 V3 V2 V4 V5 3 1 4 2 5 如果连通图是一个网络，称该网络中所有生成树中权值总和最小的生成树为最小生成树(也称最小代价生成树)。 C B A E D 32 54 16 21 69 45 36 47 40 C B A E D 32 16 21 36 生成树的实际意义 1 2 3 6 4 5 10 21 33 11 14 5 6 18 19 6 最小生成树 1 5 2 4 6 3 10 5 18 11 6 1 2 3 6 4 5 10 21 33 11 14 5 6 18 19 最小生成树算法思想一 Kruskal算法 6 1 2 3 6 4 5 10 11 5 18 6 起始条件：生成树只包含图的所有顶点。 最小生成树不一定唯一 1 2 6 4 5 10 11 5 6 18 1 2 3 6 4 5 10 21 33 11 14 5 6 18 19 最小生成树算法思想二 Prim算法 1 5 2 4 6 3 10 5 18 11 6 6 初始条件 点集合={u0}，TE={φ}。 1. TE=Ф,U={u0} 2. 当U≠V，重复下列步骤： (1)选取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保证不形成回路 (2)TE=TE+（u0,