考研笔记

板子：Kruskal

★ 级：手算为主。把边按权值从小到大排好，依次看每一条边：两个端点不在同一个连通分量里就选它，用并查集判断和合并。选够 条边就停。

代码

typedef struct {                             // Kruskal 用的边：两个端点和权值
    int u, v, w;
} KEdge;
 
int cmpEdge(const void *a, const void *b) {  // qsort 的比较函数：按权值从小到大
    return ((KEdge *)a)->w - ((KEdge *)b)->w;
}
 
int Kruskal(KEdge e[], int m, int n) {       // n 个顶点、m 条边；返回 MST 的总权值，不连通时返回 -1
    qsort(e, m, sizeof(KEdge), cmpEdge);     // ① 边按权值升序（排序不是本题重点，直接用 C 库的 qsort）
    int S[MAXV];
    Initial(S, n);                           // ② 并查集：每个顶点自成一个连通分量
    int sum = 0, cnt = 0;                    // cnt：已经选了几条边
    for (int i = 0; i < m && cnt < n - 1; i++) {
        int r1 = Find(S, e[i].u), r2 = Find(S, e[i].v);
        if (r1 == r2) continue;              // 两端已经连通：再加这条边就成环，舍弃
        Union(S, r1, r2);                    // ③ 选这条边，合并两个连通分量
        sum += e[i].w;
        cnt++;
    }
    return cnt == n - 1 ? sum : -1;          // 选不够 n-1 条边：图不连通
}

Initial、Find、Union 用的是 并查集 那一篇的教材口径写法。

复杂度：排序 ，并查集部分接近 ，总时间 。适合边稀疏的图。

关键边界

位置为什么
比较的是两端的根 Find(u) 和 Find(v)根相同才说明在同一个连通分量里。直接比较 S[u] 和 S[v] 是错的
cnt < n - 1 就停生成树恰好有 条边，选够了后面的边都不用再看
cnt != n - 1 返回 边都看完了还选不够，说明图不连通，只有生成森林
cmpEdge 返回差值负数表示 a 排在前面。权值不大时可以直接相减，否则可能溢出

易错点

  • 权值相等的边可能让最小生成树不唯一，但总权值一定唯一。
  • Prim 适合稠密图（，和边数无关），Kruskal 适合稀疏图（）。选择题常考这一对。

链接

反向链接