Kruskal算法

What · 是什么

Kruskal 算法求无向带权连通图的最小生成树（MST，边权和最小的生成子图；不连通图为生成森林）。流程：把全部边按权值非降排序；用并查集维护当前已加入的边形成的连通分量；从小到大遍历每条边 (u,v,w)，若 u、v 尚不连通（加入不成环）则选取该边并合并，直到选满 n−1 条边。时间复杂度 O(E log E)（排序主导）+ O(E α(n))（并查集近常数）。正确性由切边性质/循环不变式保证。

Why · 为什么

How · 实现

伪代码

class DSU: find / union
# 输入: n 个顶点, edges 为 (u,v,w) 列表
def kruskal(n, edges):
  sort edges by w 升序
  dsu = DSU(n); total = 0; cnt = 0
  for u, v, w in edges:
    if dsu.union(u, v):        # 不成环才成功合并
      total += w; cnt += 1
      if cnt == n - 1: break
  if cnt < n - 1: 不连通（图不连通）
  return total

Python 实现

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def union(self, a, b):
        """返回 True 表示成功合并（原不连通）。"""
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.par[b] = a
        self.sz[a] += self.sz[b]
        return True


def kruskal(n, edges):
    """返回 MST 边权和；图不连通（无法形成生成树）返回 None。
    edges: (u, v, w) 列表，顶点 0..n-1。
    """
    edges = sorted(edges, key=lambda e: e[2])
    dsu = DSU(n)
    total = 0
    cnt = 0
    for u, v, w in edges:
        if dsu.union(u, v):
            total += w
            cnt += 1
            if cnt == n - 1:
                break
    return total if cnt == n - 1 else None


if __name__ == "__main__":
    # 经典图：答案由 1+2+2+5 组成
    edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
    assert kruskal(5, edges) == 10

    # 暴力交叉验证（小图穷举所有生成树）
    import itertools

    def brute_mst(n, edges):
        best = None
        for r in range(len(edges) + 1):
            for combo in itertools.combinations(edges, r):
                if len(combo) != n - 1:
                    continue
                dsu = DSU(n)
                ok = True
                cost = 0
                for u, v, w in combo:
                    if not dsu.union(u, v):
                        ok = False
                        break
                    cost += w
                if ok:
                    best = cost if best is None else min(best, cost)
        return best

    import random
    random.seed(0)
    for _ in range(30):
        n = random.randint(2, 6)
        es = []
        for u in range(n):
            for v in range(u + 1, n):
                if random.random() < 0.6:
                    es.append((u, v, random.randint(1, 20)))
        got = kruskal(n, es)
        expect = brute_mst(n, es)
        assert got == expect, (n, es, got, expect)

    # 不连通情形
    assert kruskal(3, [(0, 1, 1)]) is None
    # 单点
    assert kruskal(1, []) == 0

    print("All tests passed.")

易错点

• 排序必须按边权非降序，漏排序或不排序会直接错
• 并查集 union 返回是否合并成功，别在 union 失败时仍累加 total
• 提前终止条件是 cnt==n−1（MST 边数），不是遍历完所有边
• 不连通判定：遍历完 cnt<n−1 则返回 None/输出不连通提示
• 顶点编号从 0 开始要统一，读入 1-based 需减 1
• 边很多时排序用 key=lambda 而非 tuple 重排，避免结构体比较开销

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/mst/
• CP-Algorithms✓ https://cp-algorithms.com/graph/mst_kruskal.html
• 书籍✓ CPH ch15 Spanning trees, pp.143-146