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

Question

我希望有人能给我一个通用的方法来计算 MST 的问题，该问题的输入格式如下：

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

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

Answer 1

您真的需要使用 Prim 的吗？

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

Answer 2

如果你有一个密集的图（一个有很多边的图），Prim 的算法会更快。如果使用邻接矩阵，Prim 算法的复杂度为O(|V|^2).

这可以通过使用具有由邻接表表示的图的二进制堆数据结构来改进。使用这种方法，复杂度将是O(|E|log|V|).

使用带有邻接表的斐波那契堆数据结构会更快，复杂度为O(|E| + |V|log|V|).

注：E指图中边数，而V指图中顶点数。

STL已经实现了二进制堆数据结构，std::priority_queue. Astd::priority_queue调用heap算法库中的算法。您还可以使用 a std::vector（或任何其他具有随机访问迭代器的容器）并调用make_heap、push_heap、pop_heap等。这些都在算法库中。更多信息在这里：http ://www.cplusplus.com/reference/algorithm/ 。

您也可以实现自己的堆数据结构，但这可能太复杂且不值得性能优势。