最小生成树相关算法在计算机程序设计竞赛中的研究

曲大鹏，侯振桓，宣伟宏，宋宝燕

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引言

一个连通图的生成树是图的极小连通子图，它包含图中的所有顶点，并且只包含保持图连通的最少的边.若去掉它的一条边，就会使生成树变成非连通图，若增加它的一条边，就会在图中形成一条回路.对于一个无向带权连通图G=(V，E)，生成树不同，每棵树的权(即树中所有边的权值之和)也可能不同.设K为G的所有生成树的集合，若T为K中的权值最小的那棵，则T称为G的最小生成树(Minimum Spanning Tree，MST)[1].

最小生成树具有以下性质：

1)最小生成树不是唯一的.

2)最小生成树的边的权值之和是唯一的.

3)最小生成树的边数为顶点数减1.

1 最小生成树算法

最小生成树常用的算法有普里姆Prim算法和克鲁斯卡尔Kruskal算法[2，3].为方便分析，我们设定一个无向带权连通图G=(V，E)，V为其顶点集合，E为边集合.

1.1 Prim算法

Prim算法是维护一个在最小生成树中的点的集合，从某个起始点出发，不断选择并添加离集合最近的点，直到覆盖所有要加入的点.

Input：G.

Output：MST(Vnew，Enew).

1)初始化：Vnew={x}，其中x为集合V中的任一节点(起始点)，Enew={}，为空；

2)重复下列操作，直到Vnew=V：

a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V(如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一)；

b.将v加入集合Vnew中，将边加入集合Enew中；

3).输出：使用集合Vnew和Enew来描述所得到的最小生成树.

接下来用一个简单示例来演示Prim算法，如图1所示.

Step 1：初始u={A}，v={B，C，D，E，F}，选择权值最小的边，并将C加入u集合；

Step 2：u={A，C}，v={B，D，E，F}，选择权值最小的边，并将F加入到u集合；

Step 3：u={A，C，F}，v={B，D，E}，选择权值最小的边，并将D加入到u集合；

Step 4：u={A，C，D，F}，v={B，E}，选择权值最小的边，并将B加入到u集合；

Step 5：u={A，B，C，D，F}，v={E}，选择权值最小的边，并将E加入到u集合；至此得到G的一棵最小生成树.

时间复杂度：o(v×v)，不依赖于边，所以适合于稠密图.

1.2 Kruskal算法

Kruskal算法则是以边为切入点，维护一个在最小生成树中的边的集合，初始为空，不断选择并添加不在集合中且不会让集合中的边构成回路的最短边，直到生成一个连通图.

1)新建图Graphnew，Graphnew中拥有原图中相同的全部顶点，但没有边

2)将原图Graph中所有边按权值从小到大排序

3)循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中如果这条边连接的两个节点于图Graphnew中不在同一个连通分量中添加这条边到图Graphnew中同样，应用一个直观的图例来演示该算法，如图2所示.

Step 1：选择权值最小的边，并保证A，C不在同一个集合中，然后合并AC；

Step 2：选择权值最小的边，并保证D，F不在同一个集合中，然后合并DF；

Step 3：选择权值最小的边，并保证C，F不在同一个集合中，然后合并CF；

Step 4：选择权值最小的边，并保证B，E不在同一个集合中，然后合并BE；

Step 5：选择权值最小的边，并保证B，C不在同一个集合中，然后合并BC；至此得到G的一棵最小生成树.

时间复杂度：

通常在Kruskal算法中，采用堆来存放边的集合，则每次选择最小权值的边只需要O(loge)，e为图中的边数，所以总的时间复杂度为o(e×loge)，比较适合边稀疏而顶点较多的图.

1.3 Prim与Kruskal的比较

Prim算法与Kruskal算法的复杂度和策略等比较如表1所示.

表1 Prim算法与Kruskal算法的复杂度和策略比较

1.4 算法优化

1.4.1 Prim算法的二叉堆优化

在Prim算法中，我们需要在当前已确定的点集合中选择能够到达的最小权值边，普通Prim采取的是遍历不在集合中的点，需要o(v)的时间复杂度，我们不妨改用邻接表来存储边，把每次增加一个点后产生的边用二叉堆来维护，同样每次也从二叉堆中取出一条不会构成环的最小权值边，一共有e条边，每次存取边操作均摊为o(logv)，复杂度缩减为o(e×logv).

1.4.2 Prim算法的斐波那契堆优化

我们还可以进一步用斐波那契堆来维护能够到达的边，在斐波那契堆中插入一个值和查询一个值的复杂度均为o(1)，删除一个值的复杂度为o(logv)，易知一共需要删除v-1条边，复杂度进一步缩减为o(e+v×logv)，尤其是在稠密图中，较显著地提高了运行速度.但由于斐波那契堆较难实现，在解题中一般采用上一个优化.

1.4.3 Kruskal算法的并查集优化

对Kruskal的优化主要体现在对并查集的优化上，并查集的本质是一颗树，当树的深度过大时，每次使用并查集的时间复杂度将会很大，因此我们在每次查找祖先时，可以把查找路径上每个节点的父亲变成与其祖先相同，这样处理后使每次合并与查找的复杂度均摊为o(logv)，总复杂度为o(v×logv+e×loge).

2 算法选择与应用

2.1 算法选择

从以上讨论可以看出，Prim算法更加适合于节点数较少的稠密图，而Kruskal算法更加适合于稀疏图.由于Kruskal算法在构建最小生成树的选择策略是每次由小到大的添加边，所以我们可以得到最小生成树的边的大小关系；而Prim算法是每次去选择一个节点来扩充当前的连通块，这在处理与节点相关的题目时，逻辑上较为简单.

2.2 程序设计实例

根据前面的分析，我们针对最小生成树相关的几个主要问题，从国内的主要oj平台，选择合适题目进行说明和验证.

2.2.1 基本最小生成树问题

Agri-Net[4]是在N个互相连通的农场中间安装光纤，要求能将所有农场都连通起来，并且要使光纤距离最小，输出安装光纤的总距离.可以明显看出此题为典型的基本最小生成树问题，并且题目中未出现明显限制，因此，用两种算法都可以解答.

2.2.2 需要优化的最小生成树问题

Hihocoder1109[5]也是基本的最小生成树问题，但由于其节点的数量最多可达105，边的数量最多可达106，且单组数据的时限为1 s，使用基本最小生成树算法则会超过时限.我们可以应用上文中分析的三种优化算法，应用二叉堆优化的Prim算法可以顺利通过，应用并查集优化的Kruskal算法也能勉强在时限内通过本题.应用斐波那契堆优化的Prim算法虽然也可以通过本题，但其代码复杂度过高，不建议使用.

2.2.3 最小生成树中最大边问题

Highways[6]需要求出的是图中最小生成树的最大边.这里涉及到关于最小生成树的最长边为所求的证明，由于前面已分析最小生成树算法过程，通过反证法即可直接证明，证明略.两个算法都可以解答本题.Prim算法的优势在于该题目输入是邻接矩阵，但需要在生成树中寻找最大边.Kruskal算法的优势在于其选择策略是每次从小到大地添加边，只需要找最后添加的边即可，能更加方便地获取最小生成树的最大边.

2.2.4 求扩充边的最小权值和问题

CH 6210[7]是将给定的一棵树扩充为完全图，使所得图的最小生成树仍为这棵树，求扩充边的最小权值和.先看Kruskal的算法步骤，当选择策略选出一条边时，我们可以知道这条边会将两个连通块连接起来，同时该边的权值大于等于之前选出的边的权值，并且小于等于之后选出的边的权值.假设该边权值为w，我们可以将连接两个连通块的其它边的权值都设置为w+1.根据上面的性质可知，这些w+1的边不会取代任意一条生成树中的边，且使权值和最小.设两个连通块的节点数分别为x和y，则这两个块连接后对答案产生的贡献为(w+1)×(x×y-1)，所以在应用Kruskal算法求解本题时主要在步骤中增加一步计算该贡献即可.同时，由于Prim算法并不能保证增加边的有序性，添加边时不能统一添加成w+1的权值，而需要通过遍历来解决，会提高时间复杂度.

2.2.5 删点后的最小生树问题

此类问题是要求在一个N个节点的图中，任意地删除其中一些X(X<=N)个节点后，求出所有情况中边权值和最小的生成树.World Islands[8]是求删除其中X=1个节点后长度最小的最小生成树.该题目由于数据量较小，可以直接枚举每个点，然后求最小生成树，最后取最小值.但如果数据量较大，枚举删除节点，复杂度将会达到阶乘级.

我们不妨挖掘Prim算法的一个性质，假设选取某个节点作为起始点，根据其贪心策略，它必定会先选择使其边权和最小的N-X-1个点，那么我们枚举起始点，每次扩充到第N-X的点便终止，比较后便能得到答案.由于Kruskal的特性，导致其不方便用于求解本题.

2.2.6 最小生成树唯一性问题

最小生成树唯一性问题[9]是判断给定图的最小生成树是否唯一.直观思路是在枚举每条边时，每次求出对应包含该边的最小生成树，不过这样做复杂度非常高.我们可以先求出一棵最小生成树，再任意增加一条边，即构成一个环；再删除环中除该边外的最大权值边，不仅解除了环，而且保证了该生成树相比最小生成树增量最小，这棵生成树就是对应包含该边的最小生成树，于是我们可以枚举最小生成树不包含的边来获得本题的解.需要注意的是用每次通过搜索来获取最大权值边会花费大量的时间，我们可以考虑进行预处理，比如可以设置状态dp[x][y]记录最小生成树路径x-y上的最大边权值.Prim算法和Kruskal算法都可以搭配预处理，对于Prim算法来说，每次扩充一个点时，将该点作为路径的一个端点，已选集合中的点均是另一个端点，然后更新这些路径对应的状态；Kruskal算法则可以额外维护各个连通块中的点，稍微麻烦一些.

3 结论

本文主要介绍了最小生成树问题，对最小生成树的两种算法：PRIM算法和KRUSKAL算法进行分析与比较.最后通过对比两种算法的时间复杂度、空间复杂度、贪心策略以及算法实现过程中图的状态，从算法选择的角度得出结论：PRIM算法适合于稠密图，而KRUSKAL算法则比较适合边稀疏而顶点较多的图.本文给出了两种PRIM算法的优化策略和一种KRUSKAL算法的优化策略，并从国内的主要oj平台，选择了六道合适的题目进行对上述算法的优化与使用进行了说明和验证，证明了最小生成树算法以及优化在计算机程序设计大赛中的巨大实用价值.