仅给定顶点，如何创建一个“令人满意”的最小生成树(MST)？

Question

经典MST问题

在最小生成树（MST）问题的经典公式中，我们会得到一个顶点集V和一组边E。虽然给定V个顶点可以得到许多边，但实际上边数要比M小得多。

我的问题：暗示了边集，而不是给出

在我的情况下，我有一个V顶点集，其中每个顶点都是二维平面上的坐标（x，y）。我根本没有任何边，即集合E为空。实际上，我知道所有M条边和它们之间的距离：这是每对顶点之间的距离。因此，已知边的大小是最大的，即| E | = M。

这就是我的困境：如果V的大小| V |非常大（例如10,000），则M的值会非常快地增长。尝试使用MST算法，其中| V | = 10,000且| E | = M = 50,000,000可能导致严重的算法效率问题。

是否有一种方法可以在运行MST算法之前从最大边集E中删除/修剪/删除边，以减少找到“令人满意”的（即不一定是最优的）MST所需的时间？

可能的启发式方法

这里有一个可能性：

• 给定顶点集V，计算外接矩形
• 将矩形划分为R个小矩形
  • 例如将矩形在垂直和水平方向上分成四个(4)范围，产生16个小矩形
• 对于每个子矩形，从位于该子矩形中的所有顶点中计算MST。
• 将得到的MST连接起来生成一棵大MST。

是否有人可以建议一种有效的算法来生成令人满意的MST，仅根据顶点集？

- Moshe Rubin

Answer 1

听起来你正在尝试计算欧几里得最小生成树。

维基百科包含更高效的O(nlogn)算法，基于以下关键思想：

一个更好的在平面中找到EMST的方法是注意到它是n个点的每个Delaunay三角剖分的子图，这是一组大大减少的边：

- Peter de Rivaz