图论篇 —— 最小生成树

# 图论篇——最小生成树（Kruskal & Prim）

引入

要在 n 个村庄之间修路，让任意两个村庄都能互通，但路的总长度要最短——怎么选哪些路修？这就是最小生成树（MST）：在带权无向图中，选 n-1 条边把所有点连通，且边权和最小。

> 为什么不选 n-1 条以上？因为 n 个点只要 n-1 条边就能连通（树）；多一条就成环，只会浪费。所以最小生成树一定是「恰好 n-1 条边、无环、连通」。

---

一、两个核心算法

1. Kruskal（克鲁斯卡尔）——按边选

思路：把所有边按权值从小到大排序，一条条看，如果这条边的两个端点不在同一个集合，就选它，并把两个集合合并。用并查集判断连通。
为什么对：每次选当前最小且不形成环的边，最终得到的就是最小生成树（贪心正确性由「割」性质保证）。
复杂度：排序 O(mlogm) + 并查集，O(mlogm)，适合边少的稀疏图。

cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w; };
vector<Edge> e;
int fa[N];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
int kruskal(int n){
    sort(e.begin(), e.end(), [](Edge a, Edge b){ return a.w < b.w; });
    iota(fa, fa+n+1, 0);
    int cnt = 0, sum = 0;
    for (auto &ed : e) {
        int fu = find(ed.u), fv = find(ed.v);
        if (fu != fv) {
            fa[fu] = fv;      // 合并
            sum += ed.w; cnt++;
            if (cnt == n-1) break;
        }
    }
    return cnt == n-1 ? sum : -1;   // -1 表示图不连通
}

2. Prim（普里姆）——按点选

思路：从一个点出发，不断选「连接已选集合和未选集合的最小边」，把新点拉进集合。和 Dijkstra 很像，但松弛更新的是到「集合」的距离。
复杂度：朴素 O(n²)（稠密图），堆优化 O((n+m)logn)。
适用：点少边多的稠密图，邻接矩阵写法简单。

cpp
// 朴素 Prim，用 dist[v] 表示 v 到已选集合的最短距离
void prim(int s, int n) {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++)
            if (!done[j] && dist[j] < mn) mn = dist[j], u = j;
        done[u] = true; sum += mn;
        for (int v = 1; v <= n; v++)
            if (!done[v]) dist[v] = min(dist[v], a[u][v]);
    }
}

---

二、Kruskal 与 Prim 怎么选

场景	推荐
边数少、点多（稀疏图）	Kruskal（排序快，代码简单）
点少、边多（稠密图）	Prim 朴素版（邻接矩阵 `O(n²)`）
竞赛通用	Kruskal + 并查集，最常写

---

三、常见变种与考点

求次小生成树 / 严格次小生成树：先建 MST，再枚举非树边替换（用树上最大边）。
MST + 生成树计数：问有多少棵生成树（Kirchhoff 矩阵树定理）。
最小生成森林：图不连通时，每部分各建一棵，得到森林。
判断题/阅读题常考：MST 的边数一定 = 点-1；Kruskal 需要排序；Prim 每一步选的都是当前最小跨切边。

---

四、一句话记忆

Kruskal：边排序 + 并查集，按边贪心，适合稀疏图。
Prim：按点贪心，维护到集合的距离，适合稠密图。
两者选出的都是边权和最小的生成树。