最小生成树：构造连通网的最小代价生成树。本质就是把图中权大的边删除掉只留下
n-1
条边，或者说 从权最小的边开始进行保留，不构成环的边留下生成的数据结构。可以使用普利姆算法和克鲁斯卡尔算 法。
普利姆算法
取图中任意一个顶点
v
作为生成树的根，之后往生成树上添加新的顶点
w
。在添加的顶点
w
和已经在 生成树上的顶点v
之间必定存在一条边，并且该边的权值在所有连通顶点
v
和
w
之间的边中取值最小。 之后继续往生成树上添加顶点，直至生成树上含有 n-1
个顶点为止。
克鲁斯卡尔算法
考虑问题的出发点
:
为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地 小。具体做法是 先构造一个只含 n
个顶点的子图
SG
，然后从权值最小的边开始，若它的添加不使
SG 中产生回路，则在 SG
上加上这条边，如此重复，直至加上
n-1
条边为止。
克鲁斯卡尔算法代码实现
使用边集数组，对其按权从小到大进行排序，使用
parent
数组判断是否构成环，即如果加入一个边时两 个顶点都在parent
数组中已经存在表示形成了一个环。