我有一个大约 200000 个节点的列表，代表城市中的纬度/经度位置，我必须计算最小生成树。我知道我需要使用 Prim 算法，但首先我需要一个连通图。 （我们可以假设这些节点位于欧几里德计划中）
为了构建这个连通图，我首先想到计算完整的图，但是 (205000*(205000-1)/2 大约有 190 亿条边，我无法处理它。
然后我遇到了 Delaunay 三角剖分：事实上，如果我构建这个“Delaunay 图”，它包含一个子图，它是最小生成树，根据 Wikipedia [ 我总共有大约 600000 个边..]它最多有 3n-6 条边。 所以它可能是最小生成树算法的一个很好的起点。
另一种选择是构建一个近似连通图，但这样我可能会错过影响我的最小生成树的重要边。
在这种情况下，Delaunay 是可靠的解决方案吗？如果是这样，除了 delaunay 三角测量之外，还有其他可靠的解决方案吗？
更多信息：这个问题必须在 C 中解决。
这是通过进行 Delaunay 三角测量成功完成的，您可以在这里看到结果：https://github.com/Siirko/ACM-Paris
注意：代码有时相当难看，所以要注意。
点集的 Delaunay 三角剖分始终是这些点的 EMST 的超集。所以它绝对“可靠”*。并推荐，因为它的大小与点数成线性关系并且可以有效构建。
*当存在共圆点四元组时，三角剖分和 EMST 都不是唯一定义的，但这通常是无害的。
这里有一个大问题，即您可以访问哪些库以及您对自己作为编码员的信任程度。 （我假设您是 SO 新手，这一事实不应被视为衡量您作为程序员的整体经验的标准 - 如果是的话，那么，RIP。）
如果我们假设您无法访问 Delaunay 并且无法自己实现它，那么预先假设图的最小生成树算法不一定对您是禁区。您可以概念上获得完整的图表，但不能实际上。例如，克鲁斯卡尔算法假设您有图中所有边的排序列表；你的大部分边缘不会接近最小值，并且你不必比较所有
n^2您可以通过估计快速找到最小边缘，从而减少集合，然后进行细化。例如，如果将图形划分为
100*100pp这仍然不容易，但这可能比 Delaunay 更容易。