c++ - 在越来越大的坐标范围内运行 prim 的最快方法

Question

我希望有人能给我一个计算 MST 的通用方法，该方法适用于从格式如下的输入开始的问题:

<number of vertices>
<x> <y>
<x> <y>
...

我了解如何实现 prim 的算法，但我一直在寻找一种方法(使用 prim 的算法)需要最少的内存/时间来执行。我应该将所有内容存储在邻接矩阵中吗？如果顶点数量增加到 10,000，解决这个问题的最佳方法是什么(假设使用 prim's)？

Answer 1

您真的需要使用 Prim 的吗？

一种简单的方法是在每次添加节点时使用 Kruskal 算法重新计算生成树(仅使用先前选择的边)。由于 Kruskal 是 O(E log E) 并且在每次迭代中你将有 2*V-1 个边来计算(来自前一棵树的 V-1 + 来自新添加节点的 V)。每次插入都需要 O(V log V)。