algorithm - 节省空间的最小生成树

Question

我遇到过一个任务，基本上要求您找到所有顶点都连接的给定图形的 MST。我尝试使用 Kruskal 的算法，但我很快发现空间限制太紧，无法用 1 兆字节存储所有边，所以我也放弃了 Prim 和 Boruvka 的算法。有没有一种方法可以实现空间复杂度优于 O(E)(在本例中为 O(V^2))的任何这些算法(或任何其他 MST 算法)？

Answer 1

对于可以使用函数 w(i,j) 计算权重的情况，您可以使用 Prim 算法(https://en.wikipedia.org/wiki/Minimum_spanning_tree#Classic_algorithms)在空间 O(n) 而不是 O(n^2) 中计算最小生成树.

在每个阶段维护树中节点的集合 T，并且对于不在树中的每个节点保持从该节点到树中任何节点的最小距离。

开始时 T 是节点 0，对于每个其他节点，您计算从节点 0 到该节点的最小距离。

在每个阶段选择距离最小的不在树中的节点。现在计算从该节点到不在树中的所有其他节点的距离。如果该值小于他们当前的最小距离，则更新该最小距离。

维护 T 的存储成本为 O(n)，为不在树中的每个节点维护从树到该节点的最小距离的注释为 O(n)。