《算法合集之《最小生成树算法及其应用》》由会员分享，可在线阅读，更多相关《算法合集之《最小生成树算法及其应用》（29页珍藏版）》请在金锄头文库上搜索。
1、IOI2004 国家集训队论文 吴景岳 第 1 页 共 29 页 最小生成树算法及其应用最小生成树算法及其应用 江苏省常州高级中学 吴景岳 【摘要】 最小生成树是图论中的经典问题,也是一个重要部分，一般书上往往只介绍求最小生成树的算法，而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明， 使大家对此有更加深刻的认识。本文分三部分：一、基础篇，主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇，具体问题具体分析，侧重于思考和证明的过程。三、总结。 【关键字】 最小生成树 【目录】 一、 基础篇 1定义 2求最小生成树的一般算法 3常用算法 a) Kruska
2、l 算法 b) Prim 算法 4MaintainIOI2003 二、 应用篇 1概述 2例题 a) RobotBOI2002 b) 北极通讯网络Waterloo University 2002 三、 总结 IOI2004 国家集训队论文 吴景岳 第 2 页 共 29 页 【正文】 1基础篇 11 定义定义 在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根 电线连接两个插脚，把所有 n 个插脚连接起来，只要用 n- 1 根电线就可以了。在 所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。 把问题转化为图论模型就是：一个无向连通图 G=(V,E)，V 是插脚的集合，
3、 E 是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值 w(u,v)，表示 连接它们所需的电线长度。我们的目标就是找到一个无环的边集 T，连接其中所 有的点且使总权值最小。 总权值 =TvuvuwTw),(),()( 既然 T 是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图 G 中生成出来的，我们把它叫做生成树生成树。如果一棵生成树在所有生成树中总权值最 小，我们就把它称作最小生成树最小生成树。 12 求最小生成树的一般算法求最小生成树的一般算法 解决最小生成树问题有没有一般的方法呢？下面我们就介绍一种贪心算法。 该算法设置了集合 A，该集合一直是某最小生成树的子集。算
4、法执行的每一步， 都要决策是否把边(u,v)添加到集合 A 中， 能够添加的条件是保证 A(u,v)仍然 是最小生成树的子集。我们称像(u,v)这样的边为 A 的安全边安全边，或称这样的边对 集合 A 是安全的。 求最小生成树的一般算法流程如下： GENERIC-MST(G,w) 1. A 2. while A 没有形成一棵生成树 3. do 找出 A 的一条安全边(u,v) 4. AA(u,v) 5. return A 一开始 A 为，显然满足最小生成树子集的条件。之后，每一次循环都把 一条 A 的安全边加入 A 中，A 依然是最小生成树。 本节的余下部分将提出一条确认安全边的规则（定理 1
5、） ，下一节将具体讨 论运用这一规则寻找安全边的两个有效的算法。 IOI2004 国家集训队论文 吴景岳 第 3 页 共 29 页 图 1 一个图的割(S,V-S) 首先定义几个概念。有向图 G=(V,E)的割割(S,V- S)是 V 的一个分划。当一条边 (u,v)E 的一个端点属于 S 而另一端点属于 V- S，我们说边(u,v)通过通过割(S,V- S)。 若集合 A 中没有边通过割，就说割不妨碍妨碍集合 A。如果某边是通过割的具有最 小权值的边，则称该边为通过割的一条轻边轻边。 如图 1，集合 S 中的结点为黑色结点，集合 V- S 中的结点为白色结点。连接 白色和黑色结点的那些边为通
6、过该割的边。从边上所标的权值看，边(d,c)为通过 该割的唯一一条轻边。子集 A 包含阴影覆盖的那些边，注意，由于 A 中没有边 通过割，所以割(S,V- S)不妨碍 A。 确认安全边的规则由下列定理给出。 定理定理 1 设图设图 G(V,E)是一无向连通图，且在是一无向连通图，且在 E 上定义了相应的实数值加权函上定义了相应的实数值加权函 数数 w， 设， 设 A 是是 E 的一个子集且包含于的一个子集且包含于 G 的某个最小生成树中， 割的某个最小生成树中， 割(S,V- S)是是 G 的的 不妨碍不妨碍 A 的任意割且边的任意割且边(u,v)是穿过割是穿过割(S,V- S)的一条轻边，则
7、边的一条轻边，则边(u,v)对集合对集合 A 是是 安全的。安全的。 证明：设 T 是包含 A 的一最小生成树。如果 T 包含轻边（u,v） ，则 T 包含 A(u,v)，证明就完成了。否则，可设法建立另一棵包含 A(u,v)的最小生 成树 T，(u,v)对集合 A 仍然是安全的。 图 2 最小生成树 T的建立 图 2 示出了最小生成树 T的建立。S 中的结点为黑色，V- S 中的结点为白 色，边(u,v)与 T 中从 u 到 v 的通路 P 构成一回路。由于边(u,v)通过割(S,V- S)，因 此在 T 中的通路 P 上至少存在一条边也通过这个割。设(x,y)为满足此条件的边。 因为割不妨
8、碍 A，所以边(x,y)不属于 A。又因为(x,y)处于 T 中从 u 到 v 的唯一通 路上，所以去掉边(x,y)就会把 T 分成两个子图。这时加入边(u,v)以形成一新的生 成树 T=(T- (x,y)(u,v)。 下一步我们证明 T是一棵最小生成树。因为(u,v)是通过割(S,V- S)的一条轻 边，且边(x,y)也通过割，所以有 w(u,v)w(x,y)，因此 w(T)=w(T)- w(x,y)+w(u,v)IOI2004 国家集训队论文 吴景岳 第 4 页 共 29 页 w(T)。 但 T 是最小生成树，因此 T必定也是最小生成树。又因为 T包含 A (u,v)，所以(u,v)对 A
9、 是安全的。 （证毕） 通过定理1可以更好地了解算法GENERIC- MST 在连通图G=(V,E)上的执行 流程。在算法执行过程中，集合 A 始终是无回路的，否则包含 A 的最小生成树 就会出现一个环，这是不可能的。在算法执行中的任何一时刻，图 GA=(V,A)是 一森林且 GA的每一连通支均为树。此外，对 A 安全的任何边(u,v)都连接 GA中 不同的连通支，这是由于 A(u,v)必定不包含回路。 随着最小生成树的|V|- 1 条边相继被确定， GENERIC- MST 中第 2- 4 行的循环 也随之要执行|V|- 1 次。初始状态下，A=，GA中有|V|棵树，每个迭代过程均将 减少一
10、棵树，当森林中只包含一棵树时，算法执行终止。 下面再来看一个由定理 1 得出的推论， 下一节中论述的两种算法均使用了这 个推论。 推论推论 1 设设 G=(V,E)是一无向连通图，且在是一无向连通图，且在 E 上定义了相应的实数值加权函上定义了相应的实数值加权函 数数 w， 设， 设 A 是是 E 的子集且包含于的子集且包含于 G 的某个生成树中，的某个生成树中，C 为森林为森林 GA=(V,A)中的连中的连 通支。若边通支。若边(u,v)是连接是连接 C 和和 GA中其它某连通支的一轻边，则边中其它某连通支的一轻边，则边(u,v)对集合对集合 A 是安全的。是安全的。 证明：因为割(C,V-
11、 C)不妨碍 A，因此(u,v)是该割的一条轻边。由定理 1，边 (u,v)对集合 A 是安全的。 （证毕） 13 常用算法常用算法 GENERIC- MST 是形成最小生成树的一般算法， 不过我们需要的是更加具体 的算法。这一节具体讨论两种常用的算法：Kruskal 算法和 Prim 算法。它们虽然 都遵循所谓的“一般”算法，但在实现上有着各自的特点。 Kruskal 算法：算法： Kruskal 算法是直接建立在上一节中给出的一般最小生成树算法的基础之上 的。 该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安 全边，并把它添加到正在生长的森林中。设 C1 和 C2
12、表示边(u,v)连结的两棵树。 因为(u,v)必是连结 C1 和其它某棵树的一条轻边，所以由推论 1 可知(u,v)对 C1 是安全边。Kruskal 算法是一种贪心算法，因为算法每一步添加到森林中的边的 权值都尽可能小。 Kruskal 算法的实现可以使用并查集。每一集合包含当前森林中某个树的结 点，操作 FIND- SET(u)返回包含 u 的集合中的一个代表元素，因此我们可以通过 测试 FIND- SET(u)是否等同于 FIND- SET(v)来确定两结点 u 和 v 是否属于同一棵 树，通过过程 UNION 来完成树与树的连结。 MST-KRUSKAL(G,w) 1. A 2. fo
13、r 每个结点 vVG 3. do MAKE-SET(v) IOI2004 国家集训队论文 吴景岳 第 5 页 共 29 页 4. 根据权 w 的非递减顺序对 E 的边进行排序 5. for 每条边(u,v)E，按权的非递减次序 6. do if FIND-SET(u)FIND-SET(v) 7. then AA(u,v) 8. UNION(u,v) 9. return A Kruskal 算法的工作流程如图 3 所示。 阴影覆盖的边属于正在生成的森林 A。 算法按权的大小顺序考察各边。箭头指向算法每一步所考察到的边。第 1- 3 行初 始化集合 A 为空集并建立|V|棵树，每棵树包含图的一个结
14、点。在第 4 行中根据 其权值非递减次序对 E 的边进行排序。在第 5- 8 行的 for 循环中首先检查对每条 边(u,v)其端点 u 和 v 是否属于同一棵树。如果是，则把(u,v)加入森林就会形成一 回路，所以这时放弃边(u,v)；如果不是，则两结点分属不同的树，由第 7 行把边 加入集合 A 中，第 8 行对两颗树中的结点进行归并。 IOI2004 国家集训队论文 吴景岳 第 6 页 共 29 页 图 3 Kruskal 算法的执行流程 Kruskal 算法在图 G=(V,E)上的运行时间取决于如何实现集合的合并。 我们可 以采用路径压缩的优化方法，这是目前所知的最有效的。初始化需占用
15、时间 O(V)，第 4 行中对边进行排序需要的运行时间为 O(ElgE)；对分离集的森林要进 行 O(E)次操作，总共需要时间为 O(E(E,V)，其中函数为 Ackermann 函数的 反函数。因为(E,V)=O(lgE)。所以 Kruskal 算法的全部运行时间为 O(ElgE)。 Prim 算法：算法： 正如 Kruskal 算法一样。Prim 算法也是最小生成树一般算法的特例。它的执 行非常类似于寻找图的最短通路的 Dijkstra 算法。Prim 算法的特点是集合 A 中 的边总是只形成单棵树。如图 4 所示，阴影覆盖的边属于正在生成的树，树中的 结点为黑色。在算法的每一步，树中与树
16、外的结点确定了图的一个割，并且通过 该割的轻边被加进树中。 树从任意根结点 r 开始形成并逐渐生长直至该树跨越了 V 中的所有结点。在每一步，连接 A 中某结点到 V- A 中某结点的轻边被加入到 树中。由推论 1，该规则总是加入对 A 安全的边，因此当算法终止时，A 中的边 就成为一棵最小生成树。因为每次添加到树中的边都是使树的权尽可能小的边， 因此上述策略是“贪心”的。 有效实现 Prim 算法的关键是设法较容易地选择一条新的边添加到由 A 的边 所形成的树中，在下面的伪代码中，算法的输入是连通图 G 和将生成的最小生 成树的根 r。在算法执行过程中，不在树中的所有结点都驻留于优先级基于 key 域的队列 Q 中，对每个结点 v，keyv是连结 v 到树中结点的边所具有的最
