最小生成树

求一个图的最小生成树。

本文不面向读者。

一般是无向图？

只考虑连通图。

Kruskal

贪心。将每条边的边权从小到大排序，依次加入边。用一个并查集维护点的连通情况，如果该边两个端点尚未连通，则选择此边，否则检查下一条边。当加入 \(n-1\) 条边后，算法结束。

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

Prim

一般都写 Kruskal 的，如果为稠密图/完全图才用 Prim。故只描述暴力 Prim。

依然贪心。

类似 Dij，从任意一个点开始，维护 \(dis_i\) 表示已连通的点到点 \(i\) 的最小距离，同时维护 \(vis_i\) 表示是否连通（已选择）。每次选择一个 \(dis_u\) 最小的 \(u\)，且 \(vis_u=\text{false}\)，即 \(u\) 为被选择，那么选择 \(u\)，最小生成树权值和加上 \(dis_u\)，然后用 \(u\) 更新其他点的距离。