生成树（spanning tree）指的是从一个连通无向图中取出的一棵树（极小连通分支），这棵树的点集 V 和原来相同，但是只取了原来的图中的 v - 1 条边。而最小生成树（minimum spanning tree, MST）则是从一个连通无向图中取出一棵边权和最小的连通子树。

求解最小生成树有两种经典算法：Prim 算法和 Kruskal 算法。

Prim 算法

类似于 Dijkstra 算法（（链接未公开）），使用贪心策略，不过每次添加的是最短的边。该算法的复杂度是 O(n^2)，使用堆优化可以加速到 O(m \log n)。

算法过程

设 S 表示已经连通的点，T 表示尚未连通的点。类似于 Dijkstra 算法，维护一个 dis 数组，但是这次 dis[v] 的意义是 v 到点集 S 的距离，而不是到源点的距离。初始时，S = \varnothing，T 为全体顶点，dis 数组赋值为 +\infty，按如下步骤进行算法：

1. 取出 T 中 dis 最小的顶点 u（第一次运行时，由于 dis 均为无穷大，任取一个顶点即可）；
2. 将 u 从 T 移到 S，然后遍历 u 的出边 e = (u, v)。若 v \in T 且 e->w < dis[v]，则令 dis[v] 等于 e->w； 重复以上两步直至 T = \varnothing。

Kruskal 算法

最小生成树的另一种算法，思想是将所有边按边权从小到大排序，然后逐渐将边加入图中。

算法过程

首先从一个初始无边的图开始，维护一个并查集，记录图的连通分支（初始时所有点自己构成一个连通分支）。开结构体记录每一条边与哪两个点连通，然后将所有边按边权排序。然后循环取出边权最小的边，若该边连接的两点不连通，则将这条边加入图中，同时合并两点对应的并查集。重复取边，直至所有的点连通（即总共添加了 v - 1 条边）为止。

瓶颈生成树与瓶颈路

瓶颈生成树，指的是边权最小值最大（或最大值最小）的生成树。瓶颈路，指的是连接两点的路径中最小边权最大（或最大边权最小）的路径。

例如要让一辆货车在两个城市间运输，但每条公路都有一个限重，这时候瓶颈路的最小边权就可以确定货车能装载多少货物；与之相似，瓶颈生成树可以确定一个生成树，使得两点间的最小边权最大。

最小生成树与最小瓶颈树

最小生成树是最小瓶颈树的充分不必要条件，也即最小生成树一定是最小瓶颈树，但最小瓶颈树不一定是最小生成树。

从 Kruskal 算法的过程，即从尽可能小的边开始添加，可以看出两者的关系。

最小生成树与瓶颈路

连接最小生成树上两点的唯一路径，一定是两点间的一条最小瓶颈路。但同样地，两点的最小瓶颈路未必位于一棵最小生成树上。

这给出了一种计算瓶颈路的朴素算法：用 LCA（最近公共祖先）求出最小生成树上两节点的最短路径，然后遍历路径找到路径上的最大边权，这就是连接两个节点的最大边权最小值。

Kruskal 重构树

Kruskal 重构树是一棵和 Kruskal 算法有关的二叉树。

在 Kruskal 算法中，我们会不断添加边权最小的一条边使两个分支连通。对应地，此时我们创建一个新节点，将两棵二叉树合并成一棵新的二叉树，并且根节点的权值为此时添边的边权。

Kruskal 重构树带来了一个新的性质：连接两节点的 LCA 的节点权值一定是这两个节点的最大边权最小值。由此，我们可以在 O(\log n) 时间内找到瓶颈路。