1.最小生成树的定义

图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树 (Minimum Spanning Tree，MST) ；

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的 $n − 1$ 条边；

对于一个带权 (假定每条边上的权均为大于零的数) 连通无向图 $G$ 中的不同生成树，其每棵树的所有边上的权值之和也可能不同；

简单来说，对于一个有 $n$ 个点的图，边一定是大于等于 $n−1$ 条的，最小生成树就是在这些边中选择 $n−1$ 条出来连接所有的 $n$ 个点，且这 $n−1$ 条边的边权之和是所有方案中最小的；

2. Kruskal 算法

2.1. 思路

Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法；

假设 $G = ( V,E )$ 是一个具有 $n$ 个顶点 $e$ 条边的带权连通无向图，$T = ( U , TE )$ 是 $G$ 的最小生成树，则构造最小生成树的步骤如下；

置 $U$ 的初值等于 $v$ (即包含有 $G$ 中的全部顶点)，$TE$ 的初值为空集（即图 $T$ 中每一个顶点都构成一个分量）；

将图 $G$ 中的边按权值从小到大的顺序依次选取：若选取的边未使生成树 $T$ 形成回路，则加入 $TE$ ；否则舍弃，直到 $TE$ 中包含 $n−1$ 条边为止；

实现 Kruskal 算法的关键是如何判断选取的边是否与生成树中己有的边形成回路，这可以通过并查集来解决；

2.2 例子

首先对图中的边按照边权从小到大排序；

按照边权从小到大的顺序依次将每条边加入到最小生成树中，但不能产生回路；

依次加入 (1, 6, 1), (3, 4, 2), (2, 7, 3), (2, 3, 4) ；

当加入边 (4, 7, 5) 时，发现会产生回路，所以跳过此边；

再按照相同的方法依次加入 (1, 2, 6), (4, 5, 6) ；

当加入边 (5, 7, 7) 时，发现会产生回路，所以跳过此边；

当加入边 (5, 6, 8) 时，发现会产生回路，所以跳过此边；

至此所有结点己经加入到了最小生成树中，算法结束；

3. 实现

1. 初始化

每个点的父节点初始化为自己，$MST$ = 0 ；

2. 遍历每一条边

若边的两端点不在同一集合，合并两点，$MST$ 加上当前边；

3. 结束遍历，$MST$ 即为最小生成树的权值之和。