离散数学第2版教学课件-最小生成树.pdfVIP

13.6.2 最小生成树 定义13.13 设G是具有n个结点的带权连通图。G的生成树T的所有边的权之和为树的 权 。在图G 的所有生成树中，树权最小的那棵生成树称作最小生成树。 （a）、（b）给出了一个带权图及其最小生成树的例子。 13.6.2 最小生成树 算法13.1避圈法 设图G有n个结点，按以下步骤可以求得图G 的最小生成树。 （Kruskal算法） 1）按权值升序将图G的边排序，得到表L； 2）令S=∅； 3）在表L中依次选取下一条边e，如果e ∉S ，且S ∪{e}构成的 子图是无圈图，则令S=S ∪{e}； 4）若|S|=n−1，则算法停止，输出集合S即为所求。否则，转3）， 继续遍历表L。 可以证明，算法13.1求得的是图G的最小生成树。 例13.7 68% 80% 应用算法13.1求图G e7 的最小生成树，G如 Sed ut Sed ut perspiciatis perspiciatis 图（a）所示。 unde omnis. unde omnis. 180 175 解： （1）根据Kruskal算法，首先根据图G得到按权值的边排序表 L ： e5, e9, e2, e4, e6, e8, e7, e1, e10, e3, e11 （2）然后，令 。 （3）接下来，依次将 e5, e7, e2, e4, e6, e1 放入S 中；边e8, e9 , 被忽略， 因为它们的加入会形成圈。 （4）此时S 中有6条边，满足 |S | =n - 1 ，所以算法结束。 得到的最小生成树如图（b）所示，树权为10。 算法13.2 设图G有n个结点，按以下步骤可以求得图G 的最小生成树。 （Prim算法） 1）选出结点v，令V (T )={v }，E (T )≠∅ ； 2）在所有u ∉V (T )的结点中，若连接结点u 和w 的边e= （u，w）是最小权重边， 其中w∈V (T )则令V (T )=V (T )∪{u }，E （T）=E (T )∪{(u,w)} 3）若 |E(T)|=n−1，算法停止，输出E(T)。否则，转2），继续向树中增加新 结点。 例13.8 右左图所示的赋权图G表 示七个城市a ，b ，c ，d ， 68% 80% b a 20 b a e ，f ，g及架起城市间直 15 23 4