最小生成树

最小生成树指的是：从给定图中选定一些边，使得这些边 连通 所有节点，而且边权之和最小。其实这样的定义就暗含了这个子图是一棵树。

最小生成树有多种算法，但是不推荐用 Prim，其不能保证时间复杂度。

Kruskal

基本思想：贪心算法，从小到大加入边。具体来说：

• 把所有边按边权从小到大排序。

• 用一个并查集，维护图中任意两点是否在同一个连通块中。

• 重复：选一条最小的边，如果它连接两个连通块，就加入生成树中。

假设我们用的并查集是 $O(\alpha(n))$ 的，那么 Kruskal 的时间复杂度是 $O(m\log m)$，其中 $m$ 是边数。

Prim

基本思想：贪心算法，从小到大加入节点。就是每次我们选择一个和当前生成树邻接的、最近的节点并连接。和 Dijkstra 有点像。

Boruvka

不知道是什么...