简介

无向图 $G$ 的生成树满足以下性质：

• 包含 $G$ 中的所有节点；
• 任意两个节点都 连通；
• 具有 树 的所有性质。

对于 $n$ 个节点的无向图，其生成树一定有 $n-1$ 条边。

图 $b$ 和图 $c$ 皆为图 $a$ 的生成树。

最小生成树，即边权和最小的生成树。

Kruskal 算法

Kruskal 是一种贪心算法。

1. 将 $m$ 条边按照边权升序排序；
2. 从小到大枚举边：
   • 若此边的两个顶点未连通，则在树中加入此边，并连通两个顶点；
   • 若此边的两个顶点已连通，直接跳到下一条边。
3. 重复直到树中共加入 $n-1$ 条边。

使用 并查集 判断和维护两个顶点是否连通。

时间复杂度为 $O(m\log m)$，适用于稀疏图。

const int N = 1e6;
int n, m, fa[N];
struct edge { int x, y, len; } g[N];

bool cmp(edge x, edge y) {
    return x.len < y.len;
}

int find(int x) {
    return !fa[x] ? x : fa[x] = find(fa[x]);
}

int kruskal() {
    sort(g + 1, g + m + 1, cmp);
    int tot = 0, sum = 0;
    for (int i = 1; i <= m; i ++) {
        if (tot == n - 1) break;
        int rx = find(g[i].x);
        int ry = find(g[i].y);
        if (rx != ry) {
            tot ++, fa[rx] = ry, sum += g[i].len;
        }
    }
    // 如果存在最小生成树，则返回边权和，否则返回 -1
    return tot == n - 1 ? sum : -1;
}

Prim 算法

和 Dijkstra 算法非常类似。

$dis[u]$ 表示节点 $u$ 到树的最短距离。

1. 建立一棵只有 $1$ 号节点的树，$dis[1]=0$；
2. 选择离树最近（$dis$ 最小）的节点加入树，对该点的所有临边进行 松弛操作。重复执行直到加入 $n-1$ 条边。

时间复杂度为 $O(n^2)$，适用于稠密图。

int prim() {
    int sum = 0;
    memset(avl, true, sizeof avl);
    memset(dis, 0x7f, sizeof dis);
    dis[1] = 0;
    for (int i = 2; i <= n; i ++) {
        int minn = INF, minp = 0;
        for (int j = 2; j <= n; j ++)
            if(avl[j] && dis[j] < minn)
                minn = dis[j], minp = j;
        if (!minp) return -1;
        avl[minp] = false, sum += minn;
        for (int j = 1; j <= n; j ++)
            if (avl[j] && dis[j] > g[minp][j])
                dis[j] = g[minp][j];
    }
    return sum;
}