Boruvka

Boruvka 最小生成树 一个用得相对少的最小生成树算法。 需要注意的是只能做边权互不相同的问题。 怎么做？ 首先先将所有点看做独立的连通块。 然后对于每个联通块找到最小的一条出边，判了连通性，可以就直接合并就行了。 这样每次联通块个数每次都会变为原来的 \(\frac{1}{2}\)，所以只会做 ......

Boruvka 算法的思想基于每个点的最短邻边一定在最小生成树上。算法流程是每轮对每个连通块找到一条连向另一连通块的最短边，然后合并两端点。因为每轮连通块数量至少减半，所以一共会进行 $O(\log n)$ 轮。 相比 Kruskal 和 Prim，Boruvka 在求稠密图的最小生成树上具有优势， ......