线性求最小生成树算法学习笔记

c_legg · 2025-08-10 13:09:21 · 算法·理论

前言

神秘的算法，又是 Tarjan 的作品。

在这里，可以找到这个算法的名字：Karger-Klein-Tarjan 算法，然后在这里（这么抽象的东西居然是卡内基梅隆大学的课件？）有该算法的简写：KKT 算法。

注意 KKT（Karger-Klein-Tarjan）算法不是 KKT（Karush-Kuhn-Tucker）条件。

该算法基于 Boruvka 算法，Boruvka 算法的时间复杂度是 \Theta(m\log n)，而 KKT 算法的期望时间复杂度为 \Theta(m)，最坏时间复杂度为 \Omega(\min\{n^2, m\log n\})。

要学会 KKT，我们要先学会 Boruvka 算法，而 Boruvka 算法是由 Boruvka step 组成的。每个 Boruvka step 的时间复杂度是 \Theta(m)，它可以求出一个带权连通图的最小生成森林。

最小生成森林

一个带权连通图的最小生成森林是该图的一个子图（包含原图中所有点，但不一定包含所有边），可以不连通，当然还有一些其他性质。

但在这个算法里，最小生成森林的用处就在于：一个带权连通图的最小生成森林也是该图的最小生成树的一个子图。

然后我们还有另一个贪心的性质：对于一个结点，连接它的边中权值最小的边一定在最小生成树上（所以也可以在最小生成森林上）。

所以我们就知道怎么进行 Boruvka step 了：

对每个结点，找到连接它的边中权值最小的边，然后把它加入一个边集里。根据上面的性质，把不在这个边集里的边去掉，得到的图就是原图的一个最小生成森林。

例如（加粗的边是一次 Boruvka step 之后会选出的边）：

然后我们可以来看 Boruvka 算法，它的步骤如下（假设原图为 G）：

~~非常简单的算法。~~

然后我们可以来进行一下复杂度分析：

显然一次 Boruvka step 的时间复杂度是 \Theta(m)；
Boruvka 算法的时间复杂度取决于执行 Boruvka step 的次数，所以它的复杂度为 \Theta(mx)，x 是执行 Boruvka step 的次数；
又每次执行 Boruvka step 后节点数至少减半，所以执行次数 x=\log n；
综上 Boruvka 算法的时间复杂度为 O(m\log n)，最坏是 \Omega(\min\{n^2, m\log n\})，最好是 \Omega(m)。

~~所以讲了那么多，还没开始讲 KKT？~~

下面我们来介绍线性求最小生成树地算法。

首先我们还要引入一个叫 F 重/轻边的概念。

假设原图 G 上有一条边 (u, v)，权值为 w，然后在 G 的最小生成森林中连接 u 和 v 的路径中的权值最大的边的权值为 w_F（如果在 F 中 u 和 v 不在一个连通块里就令 w_F=\infin）。

如果 w\le w_F，边 (u, v) 就是一条 F 轻边，反之就是 F 重边。

然后我们再不加证明的写下两个引理：

对于上面定义的 G 和 F，所有 F 重边不在 G 的最小生成树中。
若 H 是 G 的一个子图，且 H 包含 G 中每条边的概率都为 p，然后 F 是 H 的一个最小生成森林，则在 G 中，F 轻边的期望数量最多为 \frac{n}{p}。

于是就有了 KKT，算法步骤如下：

对 G 做两次 Boruvka step，节点数变为 \frac{n}{4}，设这个收缩了的图为 G_1，如果 G_1 中只有一个结点，那么算法结束；
构造出 G_1 的子图 H 使得 H 包含 G_1 中每条边的概率都为 \frac{1}{2}，然后求出 H 的一个最小生成森林 F，再删除 G_1 中的所有 F 重边得到子图 G_2；
对 G_2 做同样的事。

然后 KKT 算法就结束了，我们来算一下它的复杂度。

设对于一个 n 个结点，m 条边的图，KKT 的期望操作次数为 T(n, m)，那么有：

T(n, m)\le c(m+n)+T(\frac{n}{4}, \frac{m}{2})+T(\frac{n}{4}, \frac{n}{4})

其中 c 是一个适当的常数，不等式可以用上面的引理二来解释。

以及可以用归纳法证明 T(n, m)=\Theta(m)，易证从略。

A randomized linear-time algorithm to find minimum spanning trees

Karger-Klein-Tarjan 演算法 - 演算法的分析與證明

期望线性复杂度最小生成树算法学习笔记 - 洛谷专栏

theory_lunch_presentation_KKT.pdf

最小生成树 - OI Wiki

R. C. T. Lee, S. S. Tseng, R. C. Chang, Y. T. Tsai. 算法设计与分析导论[M]. 北京：机械工业出版社，2008.