企业官网建设流程全解析

前言

最小生成树（minimum spanning tree, MST）要解决的问题是：给定一个连通的带权无向图，选出一棵包含全部顶点的树，使所有边的权值之和最小。它在网络布线、道路规划、聚类分析里都有直接应用。需要先澄清一个前提：MST 针对的是无向连通图；如果图不连通，只能得到「最小生成森林」，不存在覆盖所有顶点的生成树。

初学者常见的误解有三个。第一，把 MST 和最短路径混为一谈：MST 最小化的是「所有选中边权值之和」，不是「某两点之间的路径长度」，所以 MST 上两点间的路径不一定是原图中的最短路。第二，以为负权边会让算法失效：负权只影响最短路径算法（如 Dijkstra），Kruskal 和 Prim 对负权完全适用。第三，以为 MST 唯一：只有当所有边权互不相同时才一定唯一；有相等权值时可能存在多棵总权值相同的生成树。

本文讲两种经典算法：Kruskal（边排序 + 并查集）和 Prim（顶点扩展 + 优先队列），给出 C++17 的完整实现，并说明复杂度、适用场景和实现细节。代码按标准语义推演，没有在本机编译或运行。

一、割性质：两种算法共同的理论基础

理解 MST 只需要抓住一个结论，通常称为割性质（cut property）：把顶点集任意划分成两个非空部分 S 和 V−S，横跨这两个部分的边称为割边；在所有割边中，权值最小的那条一定属于某棵最小生成树。直观上，如果不用这条最轻的割边，就必须用另一条更重或等重的割边把两部分连起来，换回最轻的那条不会让总权值变大。

Kruskal 从「边」的角度利用这个性质：把所有边按权值从小到大排序，依次尝试加入，只要加入后不形成环就保留。不成环意味着这条边连接了两个当前不同的连通分量，它是这两个分量之间当前最轻的可用边之一。Prim 从「顶点」的角度利用同一性质：维护一个已经选入的顶点集合 S，每次选择连接 S 与 V−S 的最轻边，把新顶点并入 S。

两种算法都只需要「局部最轻」的贪心选择，正确性来自割性质，而不是某种全局搜索。理解这一点，就能明白为什么它们不需要回溯，也不需要像旅行商问题那样枚举。

二、Kruskal：排序加并查集

Kruskal 的流程非常直接：

1. 
   
2. 把所有边按权值升序排序。
3. 
   
4. 初始化并查集，每个顶点各自成为一个集合。
5. 
   
6. 依次扫描每条边，若两个端点属于不同集合，就选入这条边并合并两个集合；否则跳过（会成环）。
7. 
   
8. 选够 n−1 条边时停止；若扫描完仍不足 n−1 条，说明图不连通。
9. 
   

并查集（disjoint set union, DSU）负责「判断两个顶点是否已经连通」和「合并两个连通分量」。用路径压缩加按秩合并，单次操作的均摊复杂度接近常数，记作 O(α(n))，其中 α 是增长极慢的反阿克曼函数。

判断「成环」的另一种说法是：一条边的两个端点已经在同一个集合里，加入它就会在树上形成回路。因为生成树要求恰好 n−1 条边且无环，所以这个判断是充分的。

下面给出完整实现。注意排序比较器使用严格小于，不能写<=；std::sort要求严格弱序（strict weak ordering），违反它是未定义行为。

// 适用于 C++17
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>

class DSU {
public:
explicit DSU(int n) : parent_(n), rank_(n, 0) {
for (int i = 0; i < n; ++i) {
parent_[i] = i;
}
}

int find(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]]; // 路径减半
x = parent_[x];
}
return x;
}

bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return false;
}
if (rank_[a] < rank_[b]) {
std::swap(a, b);
}
parent_[b] = a;
if (rank_[a] == rank_[b]) {
++rank_[a];
}
return true;
}

private:
std::vector<int> parent_;
std::vector<int> rank_;
};

struct Edge {
int u;
int v;
long long weight;
};

std::vector<Edge> kruskal(int n, std::vector<Edge> edges) {
std::sort(edges.begin(), edges.end(),
[](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});

DSU dsu(n);
std::vector<Edge> mst;
if (n > 1) {
mst.reserve(static_cast<std::size_t>(n - 1));
}

for (const Edge& e : edges) {
if (dsu.unite(e.u, e.v)) {
mst.push_back(e);
if (static_cast<int>(mst.size()) == n - 1) {
break;
}
}
}
return mst; // 连通图应恰好有 n-1 条边
}

kruskal返回选中的边。调用方应检查mst.size() == n - 1，以此判断原图是否连通。边权用long long是为了降低大权值求和时溢出的风险；如果权值范围明确可控，用int也可以，但总权值仍建议用更宽的类型累加。

三、Prim：从顶点集合向外扩展

Prim 维护一个已选顶点集合，以及每个未选顶点到该集合的最小边权。每一轮取出当前最小的一项，把对应顶点加入集合，再用它的邻边更新其他未选顶点。用优先队列（std::priority_queue）取最小值，队列里可能残留同一个顶点的旧记录，所以弹出时要检查该顶点是否已经被选过，已选过就跳过。

与 Kruskal 相比，Prim 不需要对所有边排序，更适合稠密图；Kruskal 的排序开销是 O(E log E)，在稀疏图上通常更划算。两者的正确性都来自割性质。

// 适用于 C++17
std::optional<long long> prim(
int n,
const std::vector<std::vector<std::pair<int, long long>>>& adj) {
if (n <= 0) {
return 0;
}

const long long INF = std::numeric_limits<long long>::max();
std::vector<long long> best(n, INF);
std::vector<bool> used(n, false);

using Item = std::pair<long long, int>; // (边权, 顶点)
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;

best[0] = 0;
pq.push({0, 0});

long long total = 0;
int count = 0;

while (!pq.empty()) {
auto [dist, u] = pq.top();
pq.pop();

if (used[u]) {
continue; // 队列中的过期记录
}
used[u] = true;
total += dist;
++count;

for (const auto& [v, w] : adj[u]) {
if (!used[v] && w < best[v]) {
best[v] = w;
pq.push({w, v});
}
}
}

if (count != n) {
return std::nullopt; // 图不连通
}
return total;
}

返回std::optional<long long>而不是用-1表示失败，是为了避免和合法的负权总权值混淆。std::optional需要 C++17；如果项目停留在 C++14，可以改用bool返回值加输出参数。

四、完整示例与选型

下面的main用同一张图分别跑两种算法。图的顶点编号为 0 到 5，共 8 条边。

// 适用于 C++17
int main() {
const int n = 6;
std::vector<Edge> edges = {
{0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},
{2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}
};

std::vector<Edge> mst = kruskal(n, edges);

std::vector<std::vector<std::pair<int, long long>>> adj(n);
for (const Edge& e : edges) {
adj[e.u].push_back({e.v, e.weight});
adj[e.v].push_back({e.u, e.weight});
}
std::optional<long long> total = prim(n, adj);

std::cout << "edges: " << mst.size() << '\n';
if (total.has_value()) {
std::cout << "total: " << *total << '\n';
}
return 0;
}

按 Kruskal 的选择顺序，权值为 1、2、2、3 的边先被选入，最后选入权值 6 的边连接顶点 5，共 5 条边，总权值为 14。Prim 从顶点 0 出发，按割性质每次选最轻的跨割边，应当得到相同的总权值。这里是手工推演，不代表实际执行。

选型时先看 E 与 V 的关系：E 接近 V² 的稠密图用 Prim，E 接近 V 的稀疏图用 Kruskal。两者都能处理负权；如果只需要最小总权值而不需要具体边集，Prim 可以直接累加，不必保存前驱。

常见坑点

1. 
   
2. ❌ 排序比较器写成return a.weight <= b.weight;。
3. 
   

✅ 使用严格弱序return a.weight < b.weight;，相等时返回false。

1. 
   
2. ❌ 并查集的find不做路径压缩，树退化成链，复杂度明显变差。
3. 
   

✅ 在查找过程中把节点挂到更靠上的祖先，配合按秩或按大小合并。

1. 
   
2. ❌ 顶点编号从 1 开始，却用DSU dsu(n)只开了 0 到 n−1。
3. 
   

✅ 统一编号；若输入是 1-based，构造DSU(n + 1)或先减一。

1. 
   
2. ❌ 图不连通时仍然认为返回的边集是生成树。
3. 
   

✅ 检查mst.size() == n - 1；Prim 检查访问计数是否等于 n。

1. 
   
2. ❌ 用-1表示 Prim 失败，结果合法的负权总权值也被当成失败。
3. 
   

✅ 用std::optional、布尔返回值或单独的bool输出参数。

1. 
   
2. ❌ 累加总权值时用int，大图或大权值下发生有符号溢出，属于未定义行为。
3. 
   

✅ 用long long累加，并确认上界不会超过long long的范围。

1. 
   
2. ❌ Prim 弹出优先队列元素后不检查used[u]，用旧距离重复计入总权值。
3. 
   

✅ 弹出时先判断该顶点是否已加入集合，已加入就跳过。

1. 
   
2. ❌ 有重边或自环时直接假设没有，导致并查集或邻接表处理出错。
3. 
   

✅ 自环在 Kruskal 中会被unite判为同集合而跳过，重边保留不影响正确性；但仍应确认输入约定。

总结

最小生成树的实现并不复杂，真正容易出错的是边界：不连通、编号基准、溢出、比较器严格弱序、优先队列的过期记录。把割性质想清楚，再把这些工程细节逐条核对，两种算法都能稳定地给出正确结果。