算法

最小生成树

概念

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

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

实现

Kruscal

贪心

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

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

时间复杂度 $O(m\log m)$

Prim

// 常数没 Kruscal 好，下周就要考蓝桥了，先不学 ;)