Kruskal 最小生成树

并查集、MST 与离线激活 · HTML

数学 / 逻辑形态

图 G=(V,E)，边权可比较；求含 |V|-1 条边的生成树 T，使边权总和最小。

识别信号

• 连接全部点并最小化总成本
• 可从候选边自由挑选
• 无向边带可排序代价
• 选边时只需判断是否跨组件
• 也可能询问节省成本或瓶颈连接

容易误判的相似信号

核心不变量

扫描到当前权重时，已选森林可扩展成某棵 MST；只接受跨越不同组件的最轻边。

状态、转移与处理顺序

Python 骨架

def kruskal(n, edges):
    p, sz = list(range(n)), [1] * n
    def find(x):
        while x != p[x]:
            p[x] = p[p[x]]; x = p[x]
        return x
    def union(a, b):
        a, b = find(a), find(b)
        if a == b: return False
        if sz[a] < sz[b]: a, b = b, a
        p[b] = a; sz[a] += sz[b]
        return True
    total, chosen = 0, []
    for w, u, v in sorted(edges):
        if union(u, v):
            total += w; chosen.append((u, v, w))
            if len(chosen) == n - 1: break
    return (total, chosen) if len(chosen) == n - 1 else None

正确性思路

1. cut property 保证跨任一当前割的最轻边属于某棵 MST。
2. 排序保证接受边不重于尚未处理的替代边。
3. DSU 拒绝组件内部边，所以森林始终无环。
4. 连通时选满 n-1 条安全边，形成最小生成树。

复杂度

边界条件

• 不连通时不存在完整 MST
• 平行边可自然竞争
• 自环总被拒绝
• 负边权不影响正确性
• 单顶点的答案为 0

错误模式

选择与排除规则

• 边列表天然给出：Kruskal 通常最直接。
• 稠密邻接矩阵：可比较 Prim。
• 目标是源到终点：先辨别 shortest path，不套 MST。
• 阈值连通查询：考虑同排序骨架的 offline DSU。

相关模板

原创微型例子

Recall prompts

• Kruskal 为什么能跳过成环边？
• cut property 如何证明安全边？
• MST 与单源最短路的目标差异是什么？

我的补充