最小生成树
题单介绍
在一个连通图上，选出若干条边构成一个新的图，使得新的图任意两点之间有且只有一条路径（树）。新的图就是原来的图的生成树。
若要使生成树的边权值之和最小，那么就称为最小生成树。
* Kruskal算法
可以很自然的想到，把边排序后从小到大选，就能选到最小的生成树。但是在选的过程中，如果这条边的两个点已经联通了，那么这条边就不能选。所以我们需要判断两个点是否联通，这可以用并查集实现。
```
每个点单独一个集合
把边从小到大排序
for 每条边e:
if e的两个顶点不在同一个集合:
合并这两个集合
ans+=e的长度
```
优点：有不少题目可能选不到n-1条边，这个算法更通用。
缺点：稍微慢一点，O(n+mlogm)
* Prim算法
类似Dijkstra算法，选一个起点。每次找一个离起点最近的点，连到起点所在的连通块。
```
集合S=所有点
d[s]=0
d[其他点]=INF
for i=1 to n:
x=S中离s最近的点
for 所有以x为起点的边x->y:
更新d[y] //这里d[y]的值与Dijkstra算法不同，其他都相同
将x从S中删去
```
优点：稍微快一点，O(m+nlogn)
缺点：更难写，且不通用，更推荐Kruskal算法