LeetCode 补充题 209. 最小生成树总权重

2026-09-14 HGNULB 约 5 分钟

文章信息 2 个分类 5 个标签

分类

补充题中等

题目描述

LeetCode 原题： ✅ 1135. 最低成本连通所有城市

给定 n 个节点的无向带权图和边列表 edges，每条边为 [u,v,w]，返回连接全部节点的最小总权重；无法连通时返回 -1。

示例 1：

输入： n = 3, edges = [[1,2,2],[2,3,3],[1,3,8]]
输出： 5

提示：

节点编号为 1 到 n。
n >= 1
允许重边。
权重为非负 32 位整数，总权重用 64 位整数。

题意分析

要用最小总费用把全部节点连通，可以只保留一棵生成树。按权重尝试加入边，同时避免形成环；如果所有可用边仍不能把分量合并成一个，就不存在满足要求的生成树。

解法：Kruskal + 并查集

核心思路

[!blue]

把每个节点先看作独立分量。按边权升序扫描，find 查询两端当前的分量代表：已经在同一分量的边会形成环，跳过；属于不同分量时就合并，并累加权重。

为什么可以每次取最便宜的跨分量边：最终生成树必须把当前分量接到外部；若先前方案用了更贵的跨分量边，可以沿产生的环换出那条边，换入当前较便宜的边，总费用不会增加。排序决定尝试顺序，并查集负责快速判断是否成环。

used 记录真正选入的边数，total 记录总费用。连通 n 个节点的树需要 n-1 条边；扫描结束不足这个数量时，当前总和只属于一片森林，必须返回 -1。

解题步骤

按边权升序排序，为每个节点建立独立的并查集分量。

查询一条边的两个端点所在分量，相同则跳过。

不同时按分量大小合并，累加边权并增加已选边数。

全部处理后，选中 n-1 条边则返回总费用，否则返回 -1。

代码实现

class Solution {
    public long minimumCost(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        int[] parent = new int[n + 1];
        int[] size = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        long total = 0;
        int used = 0;

        for (int[] e : edges) {
            int a = find(parent, e[0]);
            int b = find(parent, e[1]);

            if (a == b) {
                continue;
            }

            if (size[a] < size[b]) {
                int t = a;

                a = b;
                b = t;
            }

            parent[b] = a;
            size[a] += size[b];
            total += e[2];
            used++;
        }

        return used == n - 1 ? total : -1;
    }

    private int find(int[] parent, int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }
}

import "sort"

func minimumCost(n int, edges [][]int) int64 {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i][2] < edges[j][2]
    })
    parent, size := make([]int, n+1), make([]int, n+1)
    for i := 1; i <= n; i++ {
        parent[i], size[i] = i, 1
    }
    find := func(x int) int {
        for x != parent[x] {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    total, used := int64(0), 0
    for _, e := range edges {
        a, b := find(e[0]), find(e[1])
        if a == b {
            continue
        }
        if size[a] < size[b] {
            a, b = b, a
        }
        parent[b] = a
        size[a] += size[b]
        total += int64(e[2])
        used++
    }
    if used != n-1 {
        return -1
    }
    return total
}

复杂度分析

时间复杂度：$O(n+m\log(m+1)+m\alpha(n))$，其中 $m$ 为边数；包括并查集初始化、排序和合并查询。

空间复杂度：$O(n+m)$，包含并查集与排序辅助空间。

关键点总结

[!green]

按权重从小到大枚举边，用并查集判断两端是否已连通；仅选择连接不同分量的边，选满 n-1 条即得到最小生成树。

易错点总结

[!yellow]

累加的是实际合并分量的边，形成环的边不能计入。

总费用用 64 位整数，单条边的 32 位范围不能保证总和也在该范围内。

最后检查已选边数，不能把不连通森林的费用当作答案。

n=1 时不需要选边，结果为 0。

相似题目

题目	难度	关联与区别
1489. 找到最小生成树里的关键边和伪关键边	困难	Kruskal 与并查集可作为共同基础；该题还需判断每条边是否属于所有或部分最小生成树，本题只求一次总权重，并检查是否连通。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/529045627001

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！