Boruvka 最小生成树算法

Boruvka 在思想上算是 Kruskal 和 Prim 算法的结合，在

  1. 某个点出发的边的边权可以放在一起考虑
  2. 边权具有特殊性质

时具有较大优势。

算法流程

和 Kruskal 一样，我们维护若干个连通块。我们定义，连通块 cic_i 的最小边表示这个连通块和其他连通块之间的边里最小的边，即 min⁡w(e){e:e=(u,v);u∈ci∧v∈cj∧i≠j}\min_{w(e)}\{ e:e=(u,v);u\in c_i\land v\in c_j\land i\ne j \}

初始时，每一个点 vv 都分配一个连通块 cvc_v。

  1. 计算每一个点属于哪一个连通块，把这个连通块的最小边设为 None
  2. 遍历每一条边 e=(u,v)e=(u,v)，如果 u,vu,v 不在同一个连通块内，用 w(e)w(e) 更新这两个连通块 cu,cvc_u,c_v 的最小边
  3. 如果所有连通块的最小边都是 None，则结束；否则，将每个连通块的最小边加入答案，继续从 11 循环