最小生成树

Kruskal算法

过程：

• 把所有边根据权值大小进行排序，从权值小的边开始考虑
• 如果连接当前的边不会形成环，就选当前的边。否则就不选择
• 当边数为n-1时，便可得到最小生成树。

代码实现：

通过并查集实现

Prim算法

1. 解锁点的集合为set，解锁边的集合为heap（小根堆），初始都为空

2. 从给定点开始，开始点加入到set，开始点的所有边加入到heap

3. 从heap中弹出权值最小的边e，查看该边的另一结点x

4. 若x已在set内，舍弃e，重复步骤三

5. 若x不在set内，把x加入set，x的所有边加入heap重复步骤三

6. 当heap为空停止，得到最下生成树

代码实现：