创建仅给定顶点的 "satisfactory" 最小生成树 (MST)
Creating a "satisfactory" Minimum Spanning Tree (MST) given only vertices
经典 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中删除/修剪/删除边，减少找到"satisfactory"所需的时间（即不一定是最优的) MST?
可能的启发式
这是一种可能：
- 给定顶点集合 V，计算边界矩形
- 将矩形分割成R个更小的矩形
- 例如，将矩形垂直和水平分成四 (4) 个范围，生成十六 (16) 个较小的矩形
- 对于每个子矩形，从位于子矩形中的所有顶点计算 MST。
- 连接生成的 MST 以生成一个大型 MST。
任何人都可以建议一种有效的算法来生成令人满意的仅给定顶点集的 MST 吗？
听起来您正在尝试计算 Euclidean minimum spanning tree。
维基百科包含基于关键思想的更高效的 O(nlogn) 算法：
A better approach to finding the EMST in a plane is to note that it is a subgraph of every Delaunay triangulation of the n points, a much-reduced set of edges:
经典 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中删除/修剪/删除边，减少找到"satisfactory"所需的时间（即不一定是最优的) MST?
可能的启发式
这是一种可能：
- 给定顶点集合 V，计算边界矩形
- 将矩形分割成R个更小的矩形
- 例如，将矩形垂直和水平分成四 (4) 个范围，生成十六 (16) 个较小的矩形
- 对于每个子矩形，从位于子矩形中的所有顶点计算 MST。
- 连接生成的 MST 以生成一个大型 MST。
任何人都可以建议一种有效的算法来生成令人满意的仅给定顶点集的 MST 吗？
听起来您正在尝试计算 Euclidean minimum spanning tree。
维基百科包含基于关键思想的更高效的 O(nlogn) 算法：
A better approach to finding the EMST in a plane is to note that it is a subgraph of every Delaunay triangulation of the n points, a much-reduced set of edges: