最小生成树

Boruvka

重复以下过程：

1. 遍历原图的边集，对每条边，如果他的两个端点不连通，则用这条边的边权更新这两个连通块的“最小边”
2. 遍历所有连通块，对于每个有“最小边”的连通块，把这条边加入生成树边集中。

直到没有任何一个连通块有“最小边”。

最小生成基环树

Kruskal 也可以用来求最小生成基环树。只需要在带权并查集中额外维护一下当前的连通块是树还是基环树即可。