20. 最小生成树：普里姆算法与克鲁斯卡尔算法
聊到图论，有个问题我当年面试时被问过不下五次——最小生成树。说白了，就是在一个带权无向连通图里，找一棵树，把所有顶点都连起来，并且边的总权重最小。
你想想看，现实里这玩意儿能干嘛？铺光缆、修铁路、建电网……核心就一句话：怎么花最少的钱，把所有点都连上。
解决这个问题，有两个经典算法：普里姆（Prim） 和 克鲁斯卡尔（Kruskal）。它们思路完全不同，但都能给出正确答案。我个人习惯根据图的稠密程度来选，后面我会细说。
20.1 普里姆算法（Prim）
普里姆算法的思路，有点像“从一颗种子长成一棵树”。
具体做法：
- 随便选一个顶点作为起点，把它放进“已选集合”里。
- 每次从“已选集合”到“未选集合”的所有边里，挑一条最短的。
- 把这条边连着的那个新顶点，拉进“已选集合”。
- 重复，直到所有顶点都进来。
嗯，这里要注意：每次只扩展一个顶点，而且永远不形成环。
20.1.1 代码实现（邻接矩阵版）
#define INF 99999
#define V 5
int prim(int graph[V][V]) {
int parent[V]; // 记录每个顶点的父节点
int key[V]; // 记录到已选集合的最小边权
int visited[V] = {0};
for (int i = 0; i < V; i++) key[i] = INF;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
// 找当前 key 值最小的未访问顶点
int u = -1, min = INF;
for (int i = 0; i < V; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
u = i;
}
}
visited[u] = 1;
// 更新邻居的 key 值
for (int v = 0; v < V; v++) {
if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// 打印结果
int total = 0;
for (int i = 1; i < V; i++) {
printf("边 %d - %d 权重 %d\n", parent[i], i, graph[i][parent[i]]);
total += graph[i][parent[i]];
}
return total;
}
我的习惯：如果图比较稠密（边数接近 n²），我会优先用 Prim。因为它的时间复杂度是 O(n²)，跟边数无关，稠密图下反而比 Kruskal 快。
20.1.2 时间复杂度
| 实现方式 | 时间复杂度 |
|---|---|
| 邻接矩阵 + 普通查找 | O(V²) |
| 邻接表 + 二叉堆 | O(E log V) |
| 邻接表 + 斐波那契堆 | O(E + V log V) |
我在项目中遇到过用邻接矩阵写 Prim 的情况——顶点数只有几十个，邻接矩阵写起来最省事，性能也完全够用。没必要为了“高级”而用堆。
20.2 克鲁斯卡尔算法（Kruskal）
克鲁斯卡尔的思路完全不同。它不看顶点，只看边。
做法：
- 把所有边按权重从小到大排序。
- 从小到大依次取边，如果这条边连接的两个顶点不在同一个集合里，就把它加入生成树。
- 否则跳过（避免成环）。
- 直到选了 V-1 条边为止。
这里的关键是判断两个顶点是否连通——用并查集（Union-Find）最合适。
20.2.1 代码实现
typedef struct {
int src, dest, weight;
} Edge;
typedef struct {
int V, E;
Edge* edges;
} Graph;
// 并查集：找根
int find(int parent[], int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]); // 路径压缩
return parent[i];
}
// 并查集：合并
void unionSet(int parent[], int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
parent[rootX] = rootY;
}
// 比较函数，用于 qsort
int cmp(const void* a, const void* b) {
return ((Edge*)a)->weight - ((Edge*)b)->weight;
}
void kruskal(Graph* graph) {
int V = graph->V;
Edge result[V];
int e = 0, i = 0;
qsort(graph->edges, graph->E, sizeof(Edge), cmp);
int parent[V];
for (int v = 0; v < V; v++) parent[v] = v;
while (e < V - 1 && i < graph->E) {
Edge next = graph->edges[i++];
int x = find(parent, next.src);
int y = find(parent, next.dest);
if (x != y) {
result[e++] = next;
unionSet(parent, x, y);
}
}
// 打印结果
for (i = 0; i < e; i++)
printf("边 %d - %d 权重 %d\n", result[i].src, result[i].dest, result[i].weight);
}
我曾经踩过的坑：写 Kruskal 时忘了做路径压缩，结果 find 函数退化成 O(n)，在大图上直接超时。记住：并查集一定要做路径压缩 + 按秩合并，否则性能会崩。
20.2.2 时间复杂度
| 步骤 | 复杂度 |
|---|---|
| 边排序 | O(E log E) |
| 并查集操作 | O(E α(V)) |
| 总复杂度 | O(E log E) |
α(V) 是阿克曼函数的反函数，增长极慢，可以近似看作常数。所以 Kruskal 的瓶颈在排序上。
20.3 两种算法对比
| 对比项 | 普里姆（Prim） | 克鲁斯卡尔（Kruskal） |
|---|---|---|
| 核心思路 | 从顶点出发，逐步扩展 | 从边出发，从小到大选 |
| 依赖数据结构 | 优先队列 / 数组 | 并查集 |
| 时间复杂度 | O(V²) 或 O(E log V) | O(E log E) |
| 适用场景 | 稠密图（边多） | 稀疏图（边少） |
| 是否依赖起点 | 是 | 否 |
你想想看，如果图里顶点多但边很少，比如一个城市群只有几条主干道，那 Kruskal 排序边的代价就很小，反而 Prim 要维护一个很大的 key 数组，不划算。
20.4 知识体系图
下面这张图，帮你把两个算法的核心逻辑串起来：
20.5 选型建议
- 图比较稠密（边数接近 V²）：用 Prim，邻接矩阵版就够。
- 图比较稀疏（边数接近 V）：用 Kruskal，排序 + 并查集效率很高。
- 边权可能为负：两个算法都要求边权非负，否则不保证正确。
- 需要实时加边：Kruskal 更灵活，因为它是离线算法，可以随时加入新边重新排序。
核心要点：
- Prim 是“点扩展”，Kruskal 是“边选择”。
- 两者都是贪心算法，且都能得到全局最优解。
- 并查集是 Kruskal 的灵魂，路径压缩一定要写。
- Prim 的堆优化版本在稀疏图上也有不错表现，但代码量会大一些。
好了，最小生成树就聊到这儿。这两种算法你最好都手写一遍，光看是记不住的。我当年就是看完觉得懂了，结果面试让写 Kruskal，并查集写错了，面完才反应过来……嗯，别学我。