最小生成树

生成树：连通图的极小连通子图，它包含图中全部的 $n$ 个顶点，但只有构成一棵树的 $n - 1$ 条边。移除生成树中的任意一条边都会导致图的不连通，这是生成树的边最少特性。

最小生成树：由于生成树不止一个，那么带权图中的最小生成树就是原图中 边的权值最小的生成树。

Prim 算法
- 稠密图：朴素 Prim 算法， $O (n^{2})$
- 稀疏图：堆优化 Prim 算法， $O (m \log n)$
Kruskal 算法
- 时间复杂度 $O (m \log m)$
- 一般稀疏图采用这个方法，Kruskal 算法比 Prim 算法代码更简单

朴素 Prim 算法

算法流程：类似 Dijkstra 算法

将所有距离（点到连通块）初始化为正无穷：dist[] = INF;
循环 $n$ 次，每次找到不在当前连通块 S 中的点 dist 最小的点 t
把 t 加入集合 S，同时用 t 更新外面的点到连通块的距离 dist

正确性证明：

首先定义 安全边 的概念：对于连通图的某个割集 $C$ （也就是这个集合的任意一条边去掉后可以使得图不连通）中的 最小边权的边 $e$ 。对于原图中最小生成树的任意一个子集 $E$ ，如果 $e \notin E$ ，可以证明安全边 $e$ 加入其中后，得到的 $E \cup {e}$ 依然是最小生成树的子集。

证明：取任何一个包含 $E$ 的最小生成树 $T$ ，如果 $e \in T$ ，那么证明结束；否则设 $e = (u, v)$ ，即 $e$ 是从点 $u$ 到 $v$ 的边。由于生成树的连通性，因此可以从中找到 $u \to v$ 的一条路径 $p$ ，由于 $e \in C$ 是一条割边，那么 $u$ 和 $v$ 必然分属于割的两个点集里，因此该路径 $p$ 中一定有一条边在割集 $C$ 中，不妨设为 $e^{'}$ 。对于最小生成树 $T$ ，去掉这条边 $e^{'}$ ，再加上另一条边 $e$ 得到的新图一定也是一个无环连通图：

首先一定是连通图，因为去掉 $e^{'}$ 之后，左右都是连通图，加上连通左右的 $e$ 后自然整个就成了连通图
其次一定是无环图，在没有 $e$ 的时候两边都不存在环，加入 $e$ 后如果成环，那么 $e$ 也一定是环路中的一部分，该环就一定还会穿过割集 $C$ 所分割的两部分，与割集的定义矛盾
因此得到的新图也一定是一棵树，记为 $T^{'}$ ，并且它的权值一定不大于 $T$ ，这是由于安全边定义中的最小边权性质

根据这个引理，我们发现只要维护一个边集，每次加入一条安全边，就一定能得到某棵最小生成树。

怎么证明prim算法和kruskal算法的证明的正确性？ - 知乎 (zhihu.com)

因此在 Prim 算法中，我们将点集合划分为 当前连通块 和 其他点集构成的连通块 两部分，每次寻找不在当前连通块且距离当前连通块最近的点 $t$ ，这正是找安全边，证毕。

AC858. Prim 算法求最小生成树

核心代码：

cpp

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;

    for (int i = 0; i < n; i ++) {
        int t = -1;
        for (int j = 1; j <= n; j ++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }

        if (i) {
            res += dist[t];
        }
        st[t] = true;

        if (i && dist[t] == 0x3f3f3f3f) { // exist isolated
            return dist[t];
        }

        for (int j = 1; j <= n; j ++) {
            if (!st[j]) {
                dist[j] = min(dist[j], g[t][j]); // difference between dijkstra
            }
        }
    }

    return res;
}

分为四部分解读：

t 是不在 S 内且 dist 最小的点，第一个随便取一个方便和后面作比较
第一轮循环在后面才更新了 dist[1]，因此 res 需要舍弃第一轮循环的 dist[t]
如果某一轮循环（不是第一轮）出现了 dist[t] == INF 的情况，说明最近的点距离都是正无穷，是孤立点
最后用 t 更新不在 S 中的点到连通块 S 的距离 dist

注意：为了防止负权自环的出现，应该先将 t 加入到连通块 S 中，这样执行第四步的时候就会舍弃所有自环。

以及需要注意和 Dijkstra 算法在 min 中的不同，由于 Dijkstra 算法中 dist 表示点到 $1$ 号点的距离，因此是路径长度的累加；而这里的 dist 是到连通块的距离，也就是当前边的权重值。

堆优化 Prim 算法

用堆来维护 dist 数组，因此找最小值的操作就是 $O (1)$ 的。

由于每次选择用 t 更新其他点到连通块 S 的距离 dist 时会遍历所有边，同时将 dist 加入堆中会需要 $O (\log n)$ 的时间消耗，因此总时间为 $O (m \log n)$ 。

Kruskal 算法

算法流程：

将所有边按权重从小到大排序，快速排序时间复杂度 $O (m \log m)$
依次枚举每条边 $(u, v)$ ，只要当前 $u, v$ 不连通，将其加入集合 S
注意此时的 S 可能是多连通块的情况

快速排序算法的常数很小，即 $O (n \log n)$ 中的 $\log n$ 非常小。

算法正确性证明：

由于要求 $u, v$ 不连通，因此该边肯定是属于某个割集
同时由于按照从小到大排序，该边一定是该割集中最小边权的边（否则它之前的边会使得它失去不连通性）

参见 AC837. 连通块中点的数量可知，判断是否连通用到 并查集，单次查询的时间复杂度为 $O (1)$ 。

由于 Kruskal 算法非常简单（并查集的简单应用，甚至不需要用邻接矩阵），因此在稀疏图中常用该算法而不是堆优化的 Prim 算法。

AC859. Kruskal 算法求最小生成树

核心代码：

cpp

// ...
    for (int i = 0; i < m; i ++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        u = find(u);
        v = find(v);

        if (u != v) {
            p[u] = v;
            res += w;
            cnt ++;
        }
    }

注意这里用到了 find() 函数，复习一下：

cpp

// disjoint set union
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

p[u] = v; 就是把 u 的祖宗节点直接挂到 v 的下方了。

最小生成树 ​

朴素 Prim 算法 ​

堆优化 Prim 算法 ​

Kruskal 算法 ​

最小生成树

朴素 Prim 算法

堆优化 Prim 算法

Kruskal 算法