最小生成树分析

相关结论

• 在无向图上，两点间最大边权最小的路径一定在 MST 上；
• MST 是边权和最小的树，也是最大边权最小的树；
• 对一个边集做 MST，每加入一条新边，MST 最多改变一条边。即要么将一条边从原 MST 中移除，将新边加入；要么 MST 不变。

时间复杂度分析

Prim 算法：\(O(n^2)\)

遍历每个点，并在每个点加入集合后都更新其他所有点，朴素时间复杂度 \(O(n^2)\)，常数约为 \(2\) 。

堆优化可以将查找最小值的时间复杂度降低，但这只是常数级别的优化（因为更新操作就是 \(O(n^2)\) 的），并且会增大空间的开销。

KK 算法：\(O(m\log m)\)

先对所有边进行排序，每次选最小的一条边，用并查集 \(O(1)\) 判断两点是否在一个连通块内。瓶颈在排序，处理稠密图时复杂度会变为 \(O(2n^2\log n)\)，此时应使用 Prim。

空间复杂度分析

Prim 算法：\(O(n)\)

记录每个点的 \(d\) 数组需要开 \(O(n)\)； 若使用堆优化，可以被卡成 \(O(n^2)\)。

如图，\(1\rightarrow 5,6,7,8\cdots\) 的边权为 \(10^6\)，\(2\rightarrow 5,6,7,8\cdots\) 的边权为 \(10^6-1\)，\(3\rightarrow 5,6,7,8\cdots\) 的边权为 \(10^6-2\)，这样每次都会在队列中装入 \(n\) 个元素，并且不会弹出，还会把时间也卡住。

KK 算法：\(O(n+m)\)

并查集 \(O(n)\)，存边 \(O(m)\) 。

一些技巧

这里介绍一种统计贡献的方法：在 MST 的过程中使用 KK 算法连边的时候，统计跨越两个连通块之间的所有边，可以将每条边都只统计一次，并且满足：所统计的边的边权都比当前连上的树边边权小。