图的最小生成树

《图的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图5.4图的最小生成树难点：生成树概念的理解重点：普里姆算法、克鲁斯卡尔算法图的生成树设无向连通图G=（V，{E}），其子图G’=（V，{T}）满足：①V(G’)=V(G)n个顶点②G’是连通的③G’中无回路则G’是G的生成树判断是否是生成树：具有n个顶点的无向连通图G（１）必然包括n个顶点（２）含n-1条边（３）无回路/连通无向连通图的生成树举例举例：有如下无向连通图ACBEDF图G思考题：判断下列说法是否正确（1）图的生成树是唯一的。（2）在有n个顶点的无向图中，有n-1条边的图一定是生成树。深度优先生成树和广度优先生成树P81根据深度和广度优先搜索法进行遍历就

2、可以得到两种不同的生成树，并分别称为深度优先生成树和广度优先生成树。V0V2V3V7V4V6V1V5V1V0V3V7V4V2V5V6以V0为起始点,深度优先遍历深度优先生成树V7V3V4V2V1V6V5V0以V0为起始点,广度优先遍历广度优先生成树5.4.2网络的最小生成树P82在一个图的每条边或弧上，有时可以标上具有某种含义的数值，这种边或弧上带权的图称为网（Network）。V0V1V3V2V4V56366164525V0V1V3V2V4V566455V0V1V3V2V4V536142V0V1V3V2V4V531425如果连通图是一个网络，称该网络中所有生成树中权值总

3、和最小的生成树为最小生成树(也称最小代价生成树)。例如：铺设煤气管道问题（图形结构）假设要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，管道铺设方案。在众多可选边中，如何选择n-1条边，使总代价最小？这就是求该网络最小生成树问题。CBAED325416216945364740CBAED32162136生成树的实际意义如何构造图的最小生成树？12364510213311145618196最小生成树15246310518116请同学们思考？1236451021331114561819最小生成树算法思

4、想一Kruskal算法612364510115186起始条件：生成树只包含图的所有顶点。最小生成树不一定唯一1264510115618Kruskal算法（克鲁斯卡尔）总结Kruskal算法步骤：初始时，顶点={图中所有的顶点}，边={φ}。重复下述操作：在图的边集中按权值自小至大依次选择边，若选取的边使生成树不形成回路，则将该边加入到生成树集合中；依次类推，直到将所有顶点都连通（所有顶点都在同一连通分量上为止），这时产生的具有n-1条边的一棵最小生成树。【练习】请用kruskal算法找出下图最小生成树。练习利用克鲁斯卡尔算法构造最小生成树算出该最小生成树的代价123645

5、1021331114561819最小生成树算法思想二Prim算法152463105181166初始条件点集合={u0}，TE={φ}。1.TE=Ф,U={u0}2.当U≠V，重复下列步骤：(1)选取（u0,v0)=min{cost(u,v)

6、u∈U,v∈V-U}，保证不形成回路(2)TE=TE+（u0,v0),边（u0,v0)并入TE(3)U=U+{v0}，顶点V0并入U特点:以连通为主、选代价最小的邻接边普里姆（Prim）最小生成树算法说明：Prim算法的起始点（可不写，默认为0）练习---利用Prim算法构造最小生成树V0V1V3V2V4V56356164525算出该

7、最小生成树的代价利用Prim算法构造最小生成树步骤初始化：①②①④⑤521③3466556⑥①1③第1步：6①1③4第2步：④6①1③42第3步：5②④6①1③42第4步：23⑤②5④6①1③4第5步：利用Prim演算法找最小生成树以A点为起始点ABDCE931183119586L：AT：hDcBdCeEaFWeight:28两种生成树算法比较克鲁斯卡尔算法---------适合求边稀疏的网的最小生成树普利姆算法---------适合求边稠密的网的最小生成树本节重点理解生成树概念重点掌握prim算法和Kruskal算法构造网络的的最小生成树理解最小生成树的现实意义【练习1

8、】请对下图的无向带权图：（1）按普里姆算法求其最小生成树；（2）按克鲁斯卡尔算法求其最小生成树；（3）计算最小生成树的权值；V0V1V3V2V4V56366164225【练习2】所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。问答题试着找出下图网G的最小生成树；AEFBGDC41286920121015