我希望有人可以给我一个通用的方法来计算 MST 的问题，该问题适用于格式如下的输入:
<number of vertices>
<x> <y>
<x> <y>
...
我了解如何实现 prim 的算法，但我一直在寻找一种方法(使用 prim 的算法)将需要最少的内存/时间来执行。我应该将所有内容存储在邻接矩阵中吗？如果顶点数增加到 10,000，那么解决这个问题的最佳方法是什么(假设使用了 prim)？
最佳答案
你真的需要使用Prim的吗？
一种简单的方法是每次添加节点时使用 Kruskal 算法重新计算生成树(仅使用先前选择的边)。由于 Kruskal 是 O(E log E) 并且在每次迭代中，您将恰好有 2*V-1 条边要计算(来自前一棵树的 V-1 +来自新添加节点的 V)。每次插入都需要 O(V log V)。
关于c++ - 在不断扩大的坐标范围内运行 prim 的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16095972/