Kruskal 最小生成树算法

Kruskal 算法的动机

在构造最小生成树时，除了从顶点逐步扩展的 Prim 算法，还可以从边的角度出发。Kruskal 算法采用这样的策略：优先选择权值最小的边，只要不形成环，就将其加入生成树。不断重复，直到得到 $n-1$ 条边。这种方法直观地体现了“先选便宜边”的贪心原则。

算法步骤

给定一个连通带权无向图 $G=(V,E)$，Kruskal 算法可以表述为：

1. 将边集 $E$ 按权值从小到大排序；

2. 初始化生成树为空集 $T=\varnothing$；

3. 按顺序扫描边 $(u,v)$：

   • 若 $u,v$ 属于不同连通分量，则将 $(u,v)$ 加入 $T$；
   • 否则舍弃该边；

4. 重复，直到 $T$ 含有 $|V|-1$ 条边。

此时 $T$ 即为最小生成树。若所有边扫描完仍不足 $n-1$ 条，则原图不连通；选出的边形成最小生成森林。负边权不影响该算法。

避免成环：并查集

在算法中，需要快速判断某条边是否会形成环。方法是维护顶点所属的连通分量：

• 若边的两个端点在不同分量中，则加入边并合并分量；
• 若在同一分量中，则跳过。

常用的数据结构是并查集（Disjoint Set Union, DSU），通过路径压缩和按秩合并，能够在近似常数时间内完成查找与合并操作。

正确性

每次接受的边连接两个不同分量。取其中一个分量作割，若存在更轻的跨割边，它已在排序中被处理，不可能仍连接两个不同的当前分量。因此当前边是该割的一条最小边，可由割性质安全加入。

实现

以下函数使用 Borůvka 一节中的 DSU，无向边在边表中只存一次。非连通图返回 None。

def kruskal(n, edges):
    dsu = DSU(n)
    total, tree = 0, []
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        if dsu.union(u, v):
            total += weight
            tree.append((u, v, weight))
    return (total, tree) if len(tree) == max(0, n - 1) else None

时间复杂度

• 边排序需要 $O(m\log m)$；
• 并查集操作在 $O(m\alpha(n))$ 时间内完成，其中 $\alpha(n)$ 为反阿克曼函数，增长极慢；
• 计入初始化后，总复杂度为 $O(n+m\log(m+1))$。

因此，Kruskal 算法在稀疏图（$m$ 接近 $n$）上尤为高效。