算法

最小生成树

概念

最小生成树 $:=$ 一个的子图，满足

  • 包含原图所有点
  • 满足树特征
  • 边权总和最小

实现

Kruscal

贪心

边权升序遍历，只要边的两点未连接，就加边

边权升序用 std::sort 检测点联通性用 并查集

时间复杂度 $O(|E|\log |E|)$，适合稀疏图

Prim

  1. 随便找一个点作为初始连通分量 $T$
  2. 找到与一段连通 $T$ 另一端连通 $\bar{T}$ 的边权最小边
    1. 边加入最小生成树
    2. 另一端加入 $T$
  3. 循环 2. 直到 $T$ = 原点集
维护最小边

  1. 广搜
  2. 每轮先标记 vis[u] = true，确定当前轮の最小边
  3. 再在 q 中加边，确定下一轮の候选边
  4. vis[u] 维护轮数
  5. dis[u] 打擂台维护最小边
  6. 优先队列对候选边排序优化

时间复杂度 $O(|V|^{2})$，适合稠密图

坑点

  1. 边权两两不同 $\implies$ 最小生成树唯一
  2. 最小生成树的边权可能大于未选中的边