数据结构与算法 / 系统课时

Kruskal 怎么构造最小生成树

Kruskal 怎么构造最小生成树

当图的成本都落在边上时,Kruskal 的核心策略很直接:先看最便宜的边,只要加入它不会形成环,就把它收入生成树。并查集负责快速判断“是否成环”,最终得到总权重最小的连通骨架。

学习目标

  • 理解 Kruskal 为什么按边权从小到大选择安全边
  • 用并查集实现最小生成树并计算总权重
  • 能判断图不连通时为什么无法得到生成树

从最小边开始选安全边

最小生成树需要连接全部 VV 个顶点,并且恰好包含 V−1V-1 条边。Kruskal 先把所有边按权重升序排序,然后依次检查:若一条边连接的是两个不同连通分量,就加入它并合并分量;若两端已经连通,加入后会形成环,因此跳过。

Kruskal选边与并查集合并流程

关键点是“只在不同连通分量之间加边”。这样每次选中的都是当前能连接两个分量的最小权边,不会破坏最优性,同时并查集把环检测从遍历图降成了非常便宜的集合查询。

完整实现

下面使用边列表 (weight, u, v)。每次成功合并就累计权重,并记录选中的边;当已选边数达到 n - 1 时可以提前结束。

python
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            # 路径压缩减少后续根节点查询成本。
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        # 按大小合并,避免并查集树退化。
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
    uf = UnionFind(n)
    total = 0
    chosen = []
    for weight, u, v in sorted(edges):
        # 只有连接两个不同分量的边才是安全边。
        if uf.union(u, v):
            total += weight
            chosen.append((weight, u, v))
            if len(chosen) == n - 1:
                break
    if len(chosen) != n - 1:
        raise ValueError("图不连通,无法构造最小生成树")
    return total, chosen

if __name__ == "__main__":
    edges = [
        (1, 1, 2),
        (4, 1, 3),
        (2, 2, 3),
        (5, 2, 4),
        (3, 3, 4),
    ]
    total, chosen = kruskal(4, edges)
    print(total)
    print(chosen)

预期输出

text
6
[(1, 1, 2), (2, 2, 3), (3, 3, 4)]

按权重 1、2、3 选中的三条边已经连接四个顶点,总权重为 6。后续更重的边无需再检查,因为一棵包含四个顶点的生成树只需要三条边。

为什么它能保持最优

可以把当前已经形成的若干连通分量看成多个块。对于任意一个块,要把它和外部连接起来,跨越这个切分的最轻边一定存在于某棵最小生成树中。Kruskal 每次选择的正是某两个分量之间当前可用的最轻安全边,因此不断合并后仍能保持最优。

同权重边的处理顺序可能不同,所以最小生成树不一定唯一;但只要选择规则始终是不成环的最小权边,得到的总权重仍然是最小的。

复杂度与失败条件

排序是主要成本,时间复杂度为 O(Elog⁡E)O(E\log E);之后的并查集操作总计约为 O(Eα(V))O(E\alpha(V)),通常低于排序成本。空间复杂度为 O(V+E)O(V+E),其中边列表占 O(E)O(E),并查集占 O(V)O(V)。

如果扫描完全部边后仍不足 V−1V-1 条已选边,说明原图不连通,只能得到最小生成森林,不能得到覆盖全部顶点的最小生成树。工程上应明确区分这两种结果,而不是把不完整的边集误当成 MST。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Kruskal 怎么构造最小生成树

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通