最小生成树

定义

在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

说人话版本

在一个有权无向图中，通过删去一些边，生成得到一个新的有权无向图，保证生成的结果中所有边权重相加是最小的，同时所有点又都是连通的，那么这个结果就称为最小生成树。

生成算法

主要有两种：Kruskal 算法和 Prim 算法

Kruskal 算法

此算法可以称为“加边法”，初始最小生成树边数为 0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的 $n$ 个顶点看成独立的 $n$ 棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点 $u_i$, $v_i$ 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复 (3), 直到所有顶点都在一颗树内或者有 $n-1$ 条边为止。