克鲁斯克尔算法

Kruskal算法是一种用来查找最小生成树的算法[1],由Joseph Kruskal在1956年发表[2]。用来解决同样问题的还有Prim算法Boruvka算法英语Borůvka's algorithm等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

克鲁斯克尔算法
克鲁斯克尔算法的图解
概况
类别最小生成树
数据结构并查集
复杂度
平均时间复杂度
空间复杂度
相关变量的定义
点集
边集

步骤

  1. 新建图  中拥有原图中相同的节点,但没有边
  2. 将原图中所有的边按权值从小到大排序
  3. 从权值最小的边开始,如果这条边连接的两个节点于图 中不在同一个连通分量中,则添加这条边到图 
  4. 重复3,直至图 中所有的节点都在同一个连通分量中

证明

  1. 这样的步骤保证了选取的每条边都是桥,因此图 构成一个树。
  2. 为什么这一定是最小生成树呢?关键还是步骤3中对边的选取。算法中总共选取了 条边,每条边在选取的当时,都是连接两个不同的连通分量的权值最小的边
  3. 要证明这条边一定属于最小生成树,可以用反证法:如果这条边不在最小生成树中,它连接的两个连通分量最终还是要连起来的,通过其他的连法,那么另一种连法与这条边一定构成了环,而环中一定有一条权值大于这条边的边,用这条边将其替换掉,图仍旧保持连通,但总权值减小了。也就是说,如果不选取这条边,最后构成的生成树的总权值一定不会是最小的。

时间复杂度

通过使用路径压缩的并查集,平均时间复杂度为 ,其中  分别是图的边集和点集。

此外,如果同时使用路径压缩和按秩合并,时间复杂度可以优化到  ,其中 表示反阿克曼函数

示例

图例 说明
  ADCE是最短的两条边,长度为5,其中AD被任意选出,以高亮表示。
  现在CE是不属于环的最短边,长度为5,因此第二个以高亮表示。
  下一条边是长度为6的DF,同样地以高亮表示。
  接下来的最短边是ABBE,长度均为7。AB被任意选中,并以高亮表示。边BD用红色高亮表示,因为BD之间已经存在一条(标为绿色的)路径,如果选择它将会构成一个环(ABD)。
  以高亮表示下一条最短边BE,长度为7。这时更多的边用红色高亮标出:会构成环BCEBC、会构成环DBEADE以及会构成环FEBADFE
  最终,标记长度为9的边EG,得到最小生成树,结束算法过程。

伪代码

KRUSKAL-FUNCTION(G, w)
1    F := 空集合
2    for each 图 G 中的顶点 v
3        do 将 v 加入森林 F
4    所有的边(u, v) ∈ E依权重 w 递增排序
5    for each 边(u, v) ∈ E
6        do if u 和 v 不在同一棵子树
7            then F := F ∪ {(u, v)}
8                将 u 和 v 所在的子树合并

参考源程序

C++ 实现

以下代码基于路径压缩和按秩合并的并查集,时间复杂度  

#include <bits/stdc++.h>

struct DSU {
    std::vector<int> fa, sz;
    DSU(int n = 0) : fa(n), sz(n, 1) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    int Find(int x) { // 路径压缩
        while (x != fa[x])
            x = fa[x] = fa[fa[x]];
        return x;
    }
    bool Merge(int x, int y) { // 按秩合并
        x = Find(x), y = Find(y);
        if (x == y) return false; // 处于同一连通分量
        if (sz[x] > sz[y]) std::swap(x, y);
        fa[x] = y;
        sz[y] += sz[x];
        return true;
    }
}; // 并查集

int main() {
    int n, m; // 点数,边数
    std::cin >> n >> m;
    std::vector<std::tuple<int, int, int>> edge(m);
    // 边集,三元组分别表示边权和边的两个端点
    for (auto &[w, u, v] : edge)
        std::cin >> u >> v >> w;
    std::sort(edge.begin(), edge.end()); // 按边权升序排序
    DSU dsu(n); // 初始化并查集
    long long result = 0; // 最小生成树边权和
    for (auto &[w, u, v] : edge)
        if (dsu.Merge(u, v)) result += w;
        // 合并两个连通分量并统计答案
    std::cout << result << std::endl;
    return 0;
}

参考文献

  1. ^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction To Algorithms Third. MIT Press. 2009: 631. ISBN 978-0262258104. 
  2. ^ Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 1956, 7 (1): 48–50. JSTOR 2033241. doi:10.1090/S0002-9939-1956-0078686-7.