图的最小生成树.ppt

第五章 图,5.4 图的最小生成树难点：生成树概念的理解重点：普里姆算法、克鲁斯卡尔算法,图的生成树,设无向连通图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,思考题：,判断下列说法是否正确（1）图的生成树是唯一的。（2）在有n个顶点的无向图中，有n-1 条边的图一定是生成树。,深度优先生成树和广度优先生成树P81,根据深度和广度优先搜索法进行遍历就可以得到两种不同的生成树，并分别称为深度优先生成树和广度优先生成树。,V0,以V0为起始点,深度优先遍历,深度优先生成树,广度优先生成树,网络的最小生成树P82,在一个图的每条边或弧上，有时可以标上具有某种含义的数值，这种边或弧上带权的图称为网（Network）。,如果连通图是一个网络，称该网络中所有生成树中权值总和最小的生成树为最小生成树(也称最小代价生成树)。,例如：铺设煤气管道问题（图形结构）假设要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，管道铺设方案。在众多可选边中，如何选择n-1条边，使总代价最小？这就是求该网络最小生成树问题。,生成树的实际意义,如何构造图的最小生成树？,请同学们思考？,1,2,3,6,4,5,10,21,33,11,14,5,6,18,19,最小生成树算法思想一,Kruskal算法,6,1,2,3,6,4,5,起始条件：生成树只包含图的所有顶点。,Kruskal算法（克鲁斯卡尔）总结,Kruskal算法步骤：初始时，顶点=图中所有的顶点，边=。重复下述操作：在图的边集中按权值自小至大依次选择边，若选取的边使生成树不形成回路，则将该边加入到生成树集合中；依次类推，直到将所有顶点都连通（所有顶点都在同一连通分量上为止），这时产生的具有n-1条边的一棵最小生成树。【练习】请用kruskal算法找出下图最小生成树。,练习,利用克鲁斯卡尔算法构造最小生成树算出该最小生成树的代价,1,2,3,6,4,5,10,21,33,11,14,5,6,18,19,最小生成树算法思想二,Prim算法,6,初始条件点集合=u0，TE=。,1.TE=,U=u02.当UV，重复下列步骤：(1)选取（u0,v0)=mincost(u,v)|uU,vV-U，保证不形成回路(2)TE=TE+（u0,v0),边（u0,v0)并入TE(3)U=U+v0，顶点V0 并入U,特点:以连通为主、选代价最小的邻接边,普里姆（Prim）最小生成树算法,说明：Prim算法的起始点（可不写，默认为0）,练习-利用Prim算法构造最小生成树,算出该最小生成树的代价,利用Prim算法构造最小生成树步骤,利用Prim演算法找最小生成树,以A点为起始点,A,B,D,C,E,9,3,11,8,3,11,9,5,8,6,L：,A,T：,h,D,c,B,d,C,e,E,a,F,Weight:28,两种生成树算法比较,克鲁斯卡尔算法-适合求边稀疏的网的最小生成树普利姆算法-适合求边稠密的网的最小生成树,本节重点,理解生成树概念重点掌握prim算法和Kruskal算法构造网络的的最小生成树理解最小生成树的现实意义,【练习1】请对下图的无向带权图：（1）按普里姆算法求其最小生成树；（2）按克鲁斯卡尔算法求其最小生成树；（3）计算最小生成树的权值；,【练习2】所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。,问答题,试着找出下图网G的最小生成树；,