最小生成树：Prim 与 Kruskal

最小生成树基本概念

对于一个带权连通无向图 $G=(V,E)$ ，生成树是包含全部顶点、且没有回路的连通子图。

若图有 $n$ 个顶点，则任何生成树都恰好有 $n-1$ 条边。生成树中所有边的权值之和称为该生成树的代价；在所有生成树中，代价最小的生成树称为最小生成树（MST）。

任何带权连通无向图都至少存在一棵最小生成树。

易错点： 边权互不相同是最小生成树唯一的充分条件，但存在同权边不代表最小生成树一定不唯一。

Prim 算法从一个顶点开始，不断向外扩展。设

T=(U,E_T),

其中：

初始时任取一个顶点 $u_0$ ：

U=\{u_0\},\qquad E_T=\varnothing.

之后，每次从满足 $u\in U$ 、 $v\in V-U$ 的所有边中，选择权值最小的边 $(u,v)$ ，然后更新：

U=U\cup\{v\},\qquad E_T=E_T\cup\{(u,v)\}.

重复以上过程，直到 $U=V$ 。

重点：从“树内”到“树外”的所有边中选择权值最小的边。

注意，不是只考察刚刚加入的顶点，而是考察当前整棵树中的所有顶点与外部顶点之间的边。

书中 Prim 算法的时间复杂度为：

O(|V|^2).

该实现的复杂度与边数 $|E|$ 无关，因此尤其适合稠密图。

Prim 从某一个顶点开始不断扩张；Kruskal 不从固定顶点出发，而是按照边权从小到大依次选边。

初始时：

T=(V,\varnothing).

此时所有顶点都已存在，但没有边，每个顶点都是一个独立的连通分量。

将所有边按权值从小到大排列。每遇到一条边 $(u,v)$ ，判断 $u$ 和 $v$ 是否属于两个不同的连通分量：

一直进行到选出 $n-1$ 条边为止。

书中指出，Kruskal 算法的主要开销是对所有边按照权值排序，因此时间复杂度为：

O(|E|\log |E|).

其主要复杂度由边数 $|E|$ 决定，因此特别适合稀疏图。

二者最核心的区别是：

也可以这样记：

Prim 看“当前树往外怎么长”。
Kruskal 看“下一条最便宜的边能不能加”。