最小生成树
无向连通图才有最小生成树，最小生成树即为边权和最小的生成树。
Kruskal：
过程：
将 $m$ 条边按照权值升序，每次连接权值最小的顶点不在同一个连通块中的边。
使用并查集维护连通块，算法时间复杂度瓶颈为排序，时间复杂度：$O(m\log m)$。
Prim：
过程：
类似于 Dijkstra。
将点集划分成两部分：
- 不在已生成的“最小生成树”子集中的点。（T）
- 在已生成的“最小生成树”子集中的点。（S）
每次在 S 中选择一个最小的连接 S 和 T 集合的边连接即可。
根据选取边的时间复杂度不同，可得不同的时间复杂度：
- 暴力选取：$O(n^2+m)$。
- 二叉堆（优先队列）：$O(n\log n+m\log n)$，因为不用删除了，所以时间复杂度一致。
- 其它。
Boruvka：
基本思路为，从一个集合连出一条最短边，合并两个集合。每一轮操作，每个集合都会被合并，集合个数至少减小一半，初始共有 $n$ 个集合，时间复杂度：$O(m\log n)$。
本质上，Boruvka 用于求给定图的最小生成森林，当图连通时，即为求最小生成树。
次小生成树：
结论：次小生成树和最小生成树只有一条边不同。
瓶颈生成树（Kruskal重构树）：
将在 Kruskal 过程中连接的两点，视作生成树上两叶子，建立一个新节点作为两点的父节点。最后形成的树即为 Kruskal 重构树。
结论：
原图中，两点之间的瓶颈路的瓶颈即为 Kruskal 重构树上 LCA 的权值。
瓶颈路：路径上最小边权最大的路径/路径上最大边权最小的路径。