最小生成树
Kruskal
时间复杂度 \(O(m\log m)\)。
把所有边从小到大排序，依次考虑，对于边 \((u,v)\)，如果 \(u,v\) 已经属于一个连通块（并查集维护），加入边 \((u,v)\)，否则不加。
Prim
用优先队列优化，时间复杂度 \(O((n+m)\log n)\)。
比 Kruskal 好写，而且在稠密图上时间复杂度更优。
维护一个连通点集 S，维护散点到连通块的距离 dis（可用优先队列优化），每次选择距离连通块最近的点加入连通块。
正确性证明：为什么每次加入的边一定是最小生成树上的边呢？
假设我们加入边 e，则 e 是与连通块相连的最短的边，连通块 S 与它的补集一定有一条边相连，显然只有 e 是最优的，所以 e 一定在最小生成树上。
Boruvka
时间复杂度 \(O(m\log n)\)。
维护一个最小生成森林 \(F\)，最小边指与连通块相连的不属于该连通块的边的最小那条，开始时将每个连通块最小边设为 \(inf\)。
算法分层进行，每一层如下：
- 枚举每条边 \((u,v)\)，如果 \(u,v\) 不在一个连通块，就分别更新 \(u,v\) 所在连通块的最小边。
- 如果每个连通块都没有最小边，退出程序。
- 每个连通块加上最小边。