最小生成树 (MST) 从理论到实操：基于 Kruskal 算法

1. 题目解析与理论基础

什么是最小生成树 (Minimum Spanning Tree, MST)？

想象你要在一个拥有 $n$ 个城市的国家修建光缆，使得所有城市都能互相连通（直接或间接相连）。

  • 生成树 (Spanning Tree)：在一个图中，选出 $n-1$ 条边，将所有 $n$ 个点连接起来，且没有环的结构。
  • 最小生成树 (MST)：在所有可能的生成树中，边的权值之和最小的那一个。

结合题目

  • 输入：$n$ 个节点，$m$ 条带权无向边。可能有重边（两个点之间有多条线）。
  • 目标：选出 $n-1$ 条边，连接所有点，使权值和最小。
  • 数据范围：
    • $n \le 10^3$（点不多）
    • $m \le 10^5$（边比较多）
    • $w \le 10^9$（权重很大，注意：结果需要用 long long）

2. 算法选择：Kruskal 算法

对于这道题，我们推荐使用 Kruskal (克鲁斯卡尔) 算法。

为什么选 Kruskal？

Kruskal 算法的核心思想是 “贪心”：

  1. 我们要省钱，所以总是优先选最便宜（权值最小）的边。
  2. 如果这条边连接的两个点原本不连通，我们就选它。
  3. 如果这条边连接的两个点已经连通了（属于同一个集合），选它就会形成环（浪费钱），所以我们扔掉它。

这种基于“边”的操作非常适合题目给出的 $u, v, w$ 这种输入格式。

3. 实操步骤详解

步骤一：存储图

不像 DFS/BFS 需要邻接表，Kruskal 只需要把所有的边存到一个数组（或 vector）里即可。
我们需要定义一个结构体 Edge：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
struct Edge {
    int u, v, w; // 起点，终点，权值
};
````

### 步骤二：排序 (Sorting)

这是 Kruskal 的灵魂。我们要把所有的边按**权值从小到大**排序。

- 排序后，数组最前面的就是最便宜的边。
    

### 步骤三：并查集 (Union-Find / DSU)

这是 Kruskal 的核心工具。我们需要快速判断**两个点是否已经连通**。

- **`find(x)`**：查找 $x$ 的老大（祖先）。如果不通，老大会不一样。
    
- **`unite(x, y)`**：把 $x$ 和 $y$ 所在的两个集合合并（修路连通它们）。
    

### 步骤四：遍历与累加

1. 初始化并查集（最开始每个点都是独立的，老大是自己）。
    
2. 遍历排序后的边。
    
3. 对于每一条边 $(u, v)$：
    
    - 如果 `find(u) != find(v)`：说明它俩还没连通。**选这条边！** 把权值加到总和里，并执行 `unite(u, v)`。
        
    - 如果 `find(u) == find(v)`：说明它俩早就连通了，这条边是多余的。**跳过**。
        
4. 当选够 $n-1$ 条边时，其实就可以停止了（或者遍历完所有边）。
    

---

## 4. C++ 代码实现

下面是针对该题目的完整代码实现。

C++

```cpp
#include <iostream>
#include <vector>
#include <algorithm> // 用于 sort

using namespace std;

// 1. 定义边的结构体
struct Edge {
    int u, v, w;
};

// 比较函数，告诉 sort 函数如何排序（按权值 w 从小到大）
bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// --- 并查集 (DSU) 部分 ---
const int MAXN = 1005; // 根据题目 n <= 1000
int parent[MAXN];

// 初始化并查集
void init_dsu(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i; // 最开始，每个点的老大是自己
    }
}

// 查找函数 (带路径压缩优化)
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        // 递归寻找，并顺便把沿途的节点直接挂在老大下面（路径压缩）
        parent[x] = find(parent[x]); 
        return parent[x];
    }
}

// 合并函数
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY; // 把 X 的老大归顺给 Y
    }
}
// -----------------------

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    if (cin >> n >> m) {
        vector<Edge> edges;
        
        // 2. 读取输入
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edges.push_back({u, v, w});
        }

        // 3. 核心步骤：排序
        sort(edges.begin(), edges.end(), cmp);

        // 4. 初始化并查集
        init_dsu(n);

        // 5. 遍历边，计算最小生成树
        long long total_weight = 0; // 注意：题目权值很大，累加可能超过 int，必须用 long long
        int edge_count = 0;         // 记录选了多少条边

        for (const auto &edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int w = edge.w;

            // 如果 u 和 v 不在一个集合里（还没连通）
            if (find(u) != find(v)) {
                unite(u, v);          // 连接它们
                total_weight += w;    // 累加权值
                edge_count++;         // 计数加 1
            }
        }

        // 输出结果
        cout << total_weight << endl;
    }

    return 0;
}

5. 易错点总结

  1. 数据类型溢出：

    • 题目中 $w \le 10^9$，如果有 1000 个点，总权值可能达到 $10^{12}$。

    • C++ 的 int 最大只有 $2 \times 10^9$ 左右。

    • 必须使用 long long 类型来存储 total_weight。

  2. 并查集的初始化：

    • 不要忘记在 main 函数里调用 init_dsu(n)。如果不初始化，parent 数组全是 0，会导致逻辑错误。

  3. 图的连通性：

    • 虽然这道题保证了图是连通的，但在其他题目中，如果 edge_count < n - 1，说明图不连通，不存在生成树。

  4. 重边处理：

    • Kruskal 算法天然不怕重边。因为排好序后，权值小的重边会被选上，权值大的那条重边再被遍历时，两点已经连通了，会被自动忽略。