概念

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

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

实现

Kruscal

贪心

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

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

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

Prim

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

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