algorithm - 关于MST的一些问题

Question

我现在正在学习Minimum-Spanning-Tree这个话题，我明白了大部分，但我还有一些我不明白的东西。我正在处理无向加权图。

首先，我知道找到 MST 的成本为 O(E*log V)。现在，当我们处理平面图时，我想将其优化为线性时间 - O(V+E)。

其次，我在单位正方形中看到了 n 个点的示例，并且我成功地证明了存在权重为 O(sqrt n) 的 MST。问题是我找不到找到这个 MST 的算法。

谢谢大家，或者

Answer 1

Boruvka 的算法在平面图上运行时间为 O(V)。详情见

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsII.pdf

此外，您可以通过在 Delauney 三角剖分中计算边的 MST，在 O(n log n) 时间内计算平面中 n 个点的欧几里得 MST。