最小生成树ppt课件

1、4最小生成树及算法最小生成树及算法1v1) 树树(tree)的定义与树的特征的定义与树的特征定义定义 连通且不含圈的无向图称为树常用连通且不含圈的无向图称为树常用T表示表示. 树中的边称为树枝树中的边称为树枝. 树中度为树中度为1的顶点称为树叶的顶点称为树叶.孤立顶点称为平凡树孤立顶点称为平凡树.2v3v4v5v平凡树平凡树留意：无向图留意：无向图 例如，图 6.4.1 给出的 G1 和 G2 是树，但G3 （有圈和 G4 （不连通则不是树。 G1 G2 G3 G4图 6.4.1定理定理2 设设G是具有是具有n个顶点的图，则下述命题等个顶点的图，则下述命题等价：价：1) G是树（是树（ G无圈

2、且连通）；无圈且连通）；2) G无圈，且有无圈，且有n-1条边；条边；3) G连通，且有连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了即连通，且删去一条边就不连通了即G为最为最最小连通图）；最小连通图）；6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.2图的生成树图的生成树(或支撑树或支撑树 Spanning Tree)定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的生成树的生成树. 图图G中不在生成树的边叫做弦中不在生成树

3、的边叫做弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性是显然的必要性是显然的. 一般来讲，一个图的生成树不唯一。例如，在图6.4.2 中，(a)、(b)、(c) 均是 (d) 的生成树。(c) (d) 图 6.4.2(a) (b)（II找图中生成树的方法找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 A 避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方法成树的方法. 这种方法就是在

4、已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为止止. 这种方法可称为这种方法可称为“避圈法或避圈法或“加边法加边法” 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法成树的方法可分为两种：深探法和广探法.a) 深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是

5、否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0. 令令i=0查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例用深探法求出下图例用深探法求出下图10的一棵生成树的一棵生成树 图1001234567891011121313a) 深探法深探法图100123456789101112步骤如下：步骤如下： 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为i) 在点集在点集V中

6、任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例用深探法求出下图例用深探法求出下图10的一棵生成树的一棵生成树 3b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.

7、 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例用广探法求出下图例用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图103b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对

8、标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.令令i=0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例用广探法求出下图例用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”. 这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤直到图

9、直到图G中没有圈为止中没有圈为止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.B 破圈法破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的 .3) 最小生成树最小生成树(Minimum Spanning Tree)与算法与算法 介绍最小生成树介绍最小生成树MST的三种算法：的三种算法：避圈法（避圈法（ Kruskal算法和算法和Prim算法和破圈法算法和破圈法. A Kruskal算法算法思路如下：思路如下： 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若

10、已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树,.,121*eeeGT都是最小树都是最小树.Kruskal算法步骤算法步骤(1) 对属于对属于E的边进行排序得的边进行排序得12e ee (2) 初始化操作初始化操作0,0,0tkT（3若若t=n-1,则转则转6），否则转），否则转4）（4假设假

11、设）转（构成一回路，则做4, 1kkeTk）转（，3, 1, 1,)5(kktteTTkk（6输出输出T，w，停顿，停顿,876432eeeeee例例10用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值,.,821eee最小的边有最小的边有 任取一条任取一条 ,51ee,1e 在在 中选取权值中选取权值,.,832eee,5e最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选：73,ee;3e任取一条边任取一条边,87642eeeee会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取,7e,42ee在 中选取中选取

12、. 但但 与与 都都,86ee84,ee4e8e最小生成树的最小生成树的Prim算法算法 Prim算法思路算法思路 从任意一顶点开始，首先把这个顶点包括在生成树里，然从任意一顶点开始，首先把这个顶点包括在生成树里，然后在那些其一端已在生成树里，而另一端还未在生成树里后在那些其一端已在生成树里，而另一端还未在生成树里的边中，找权值最小的一条边，并把这条边和其不在生成的边中，找权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树中。如此进行下去，每次往树里的那个顶点包括进生成树中。如此进行下去，每次往生成树里加入一个顶点和一条权最小的边，直到把所有顶生成树里加入一个顶点和一条权最小的

13、边，直到把所有顶点都包括进生成树里点都包括进生成树里 理论上，当有两条具有相同最小权值的边可选择时，选哪理论上，当有两条具有相同最小权值的边可选择时，选哪一条都行，因此构造的最小生成树不一定唯一。但若给定一条都行，因此构造的最小生成树不一定唯一。但若给定算法，则唯一算法，则唯一Prim 算法的参考步骤 第一步 T0，w(T0)0，V v0。 第二步 对每一个点 vV V ，L(v)w(v, v0)（假设 (v, v0)E，那么 w(v, v0) = ）。 第三步 假设 V = V，输出 T0，w(T0)，停顿。否则进行下一步。 第四步 在 V V 中找一点 u，使L(u) = minL(v)

14、| vV V ，并将 V 中与 u 邻接的点记为 x，e = (x, u)。 第五步 T0T0e，w(T0)w(T0)+w(e)， V V u。 第六步 对所有 vVV ，如 w(v, u) L(v)，那么 L(v) w(v, u)，否则 L(v) 不变。 第七步 转第三步。步骤步骤uL(b)L(c)L(d)L(e)L(f)L(g)eV T0C(T0)1a415 7 28a02b9 7 28(a,b)a, b(a, b)43e532 28(a,e)a, b, e(a, b), (a, e)114c25 28(c,e)a, b, e, c(a, b), (a, e), (c, e)165d161

15、2(c,d)a, b, e, c, d(a, b), (a, e), (c, e), (c, d)416g16(d,g)a, b, e, c, d, g(a, b), (a, e), (c, e), (c, d), (d, g)537f(d, f)a, b, e, c, d, g, f(a, b), (a, e), (c, e), (c, d), (d, g), (d, f)69从顶点从顶点a开始开始结果显示于图 最小生成树的 Kruskal 算法是 1956 年由Kruskal 提出的。随后在 1957 年，领导贝尔实验室数学研究室的 Prim 创立了他的算法。 Kruskal 算法的时间复

16、杂性以 O(mlog2m) 为界，当边数较多或是一个完全图时，m (n 1)2，则时间复杂性近似于 O(n2log2n)。而 Prim 算法的时间复杂性为O(n2)，所以，如果图的连通度较高最高为完全图），以 Prim 算法较好，如果图的连通度较低，特别当 m O(n) 时，那么 Kruskal 算法更合适。 在实际应用中，还会遇到求一个赋权图的最大生成树的问题。比如，某图的边权代表的是利润或效益，则最终的问题很可能就是求其最大生成树。事实上，从上面两个算法可以看出，只要边权的选择改为从大到小，求最小生成树的算就可以用来求最大生成树了。 令令m表示边数表示边数B破圈法破圈法算法算法2 步骤如下

17、：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1.2) 加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例11用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；2e 再加上弦再加上弦e7，得到圈，得到圈 v

18、4v5v2v4,27e去掉最大的权边去掉最大的权边e6，得到一，得到一棵棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部的弦均已试过全部的弦均已试过,得最小树得最小树.运用运用连线问题连线问题 欲修筑连接个城市的铁路，已知城与城之间的铁欲修筑连接个城市的铁路，已知城与城之间的铁路造价为，设计一个线路图，使总造价最低。路造价为，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小连线问题的数学模型是在连通赋权图上求权最小的生成树。的生成树。 分组技术。分组技术是设计制造系统的一分组技术。分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把种方法，它把

19、生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工都在量少，最理想的情况是使每个零件的加工都在组内完成。组内完成。 假设有假设有 13 种零件，需在种零件，需在 9 台机器上加工。台机器上加工。在各台机器上加工的零件号在下表中给出。在各台机器上加工的零件号在下表中给出。 将这将这 9 台机器分为台机器分为 3 组，使零件跨组加工组，使零件跨组加工的情形尽量少。的情形尽量少。 机器机器123456789加工的零加工的零件件2，3，7，8，9，12，132，7，8，11，121，63，5，103，7，8，9，12，1354，104，106应用范例应用范例 解：(1) 建模 设用 Mi 表示需由机器 i 加工的零件集合。对任意两台机器 i，j，定义 i 与 j的相异度：其中“”表示对称差，分子即为在机器 i 但不在机器 j 上加工，或在机器 j 但不在机器