最小生成树 (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 算法的核心思想是 “贪心”：

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

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

3. 实操步骤详解

步骤一：存储图

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

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. 易错点总结

数据类型溢出：
- 题目中 $w \le 10^9$，如果有 1000 个点，总权值可能达到 $10^{12}$。
- C++ 的 int 最大只有 $2 \times 10^9$ 左右。
- 必须使用 long long 类型来存储 total_weight。
并查集的初始化：
- 不要忘记在 main 函数里调用 init_dsu(n)。如果不初始化，parent 数组全是 0，会导致逻辑错误。
图的连通性：
- 虽然这道题保证了图是连通的，但在其他题目中，如果 edge_count < n - 1，说明图不连通，不存在生成树。
重边处理：
- Kruskal 算法天然不怕重边。因为排好序后，权值小的重边会被选上，权值大的那条重边再被遍历时，两点已经连通了，会被自动忽略。