如何在给定包含 200,000 个节点的列表中构建最小生成树？

Question

问题

我有一个包含大约200,000个节点的列表，表示城市中的纬度/经度位置，我需要计算最小生成树。我知道我需要使用Prim算法，但首先我需要一个连通图。（我们可以假设这些节点在一个欧几里得平面上）

为了构建这个连通图，我首先考虑计算完全图，但是（205,000 * (205,000-1)/2 约为190亿条边），我无法处理那么多边。

选项

然后我遇到了德劳内三角剖分：如果我构建这个“德劳内图”，它包含一个子图，该子图是根据最小生成树的定义，并且总共有约600,000条边，根据维基百科的说法[...]最多有3n-6条边。因此，这可能是最小生成树算法的一个很好的起点。

另一个选择是构建一个近似连通的图，但这样做可能会错过对我的最小生成树产生重要影响的边。

我的问题

在这种情况下，Delaunay是一个可靠的解决方案吗？如果是这样，除了Delaunay三角剖分之外，是否还有其他可靠的解决方案？

进一步信息：这个问题必须用C语言解决。

更新

通过进行Delaunay三角剖分成功解决了这个问题，你可以在这里看到结果：https://github.com/Siirko/ACM-Paris

注意：有时代码可能相当丑陋，请注意。

- Siirko

---

边缘成本只是欧几里得距离吗？ - Edward Peters

通常情况下，虽然维基百科并不完全准确，但它通常比StackOverflow的答案更可靠 - 因此，如果维基百科上有相关信息，您可以相信它而不必问我们。不过我认为这很难实现。如果您有一个可以为您完成此操作的库，那就太好了。 - Edward Peters

请执行 Delaunay 算法。 - user1196549

@EdwardPeters：排版毫无疑问。 - user1196549

@ravenspoint 构建一个连通图，它不会与完全图相比拥有所有的边，但可能会缺失对我的 MST 结果产生重要影响的边。 - Siirko

Answer 1

点集的Delaunay三角剖分始终是这些点的最小生成树的超集。因此它是绝对“可靠”的*。并且建立起来很高效，且大小与点的数量成线性关系。

*当存在共圆点四元组时，三角剖分和最小生成树都没有唯一定义，但这通常是无害的。

- user1196549

---

它在库中是否普遍可用，如果不是，那么实现起来有多容易？我开始阅读维基百科文章，但感到有些害怕。 - Edward Peters

@EdwardPeters：我最喜欢的版本是Guibas＆Stolfi的版本，它非常可靠。不幸的是，他们的文章侧重于一种非常难以理解的强大数据结构。实际上，一个更轻量级的版本——四边形边缘（quad-edge）已经足够了。应该存在一些现成的实现。 - user1196549

Answer 2

这里有一个很大的问题，就是你能够访问哪些库以及你作为编程人员的信任程度。 （我假设你在SO上是新手并不代表你整体的编程经验 - 如果是这样的话，那就RIP了。）

如果我们假设你无法访问Delaunay并且无法自行实现它，则预先假定图形的最小生成树算法并不一定对你不可用。您可以在概念上拥有完整的图形，但实际上并非如此。例如，Kruskal's算法假定您拥有所有边缘的排序列表; 您的大多数边缘都不接近最小值，并且您不必比较所有n ^ 2个来查找最小值。

您可以通过给您提供减少集合的估计然后进行细化来快速找到最小边缘。例如，如果将图形分成100 * 100网格，则对于图形中的任何点p，与p相同网格方格中的点保证比三个或更多方格远的点更近。这会使您需要比较的点集合大大减小，从而可以安全地知道您已找到最接近的点。

这仍然不容易，但可能比Delaunay更容易。

- Edward Peters

---

检查周围的八个方块可能是不够的。 - user1196549

如果是这样，那就挂了。你让我感到惊讶。但是你做得很正确，没有做出同样的假设。 - WestCoastProjects

@YvesDaoust，发现得好，已更新。 - Edward Peters

@EdwardPeters 我没有访问任何库的权限。 - Siirko

除了网格化，kD树也可以作为加速设备。 - user1196549