algorithm - 边权重范围已知时的 Prim 算法

Question

假设图中的所有边权重都是 1 到 |V| 范围内的整数。你能让 Prim 的算法运行多快？如果对于某个常数 W，边权重是 1 到 W 范围内的整数怎么办？

我认为由于 Prim 的算法是基于最小堆的实现，所以关于边权重的知识无助于加快过程。这个对吗？

Answer 1

我认为解决这个问题的主要思想是记住W是一个常数，因此，如果您将优先级队列表示为某个大小受W限制的结构，则在每次迭代时遍历整个列表不会改变您的时间复杂度算法...

例如，如果您将优先级队列表示为具有W + 1 个位置的数组T，则在每个位置都有一个顶点链接列表，使得T[i]是一个列表，其中所有顶点的优先级等于i并使用T [W + 1]存储优先级等于无限的顶点，您将采取

O(V)构建您的优先级队列（只需将所有顶点插入列表T[W+1]）

O(W)提取最小元素（只需旅行T搜索第一个非空位置）

O(1)减少键（如果顶点v的键等于i并且它已更新为j，只需从列表T[i]中取出v并插入到列表T[j]的第一个位置）。

所以，它会给你复杂度O(VW + E)而不是O(V logV + E)。

（当然，如果范围是从 1 到V ，它将不起作用，因为V^2 + E大于V \logV + E）。

Answer 2

有了这个约束，您可以实现一个使用O(V)/O(W)分别空间但具有O(1)插入和O(1)提取最小操作的堆。实际上，您可以获得O(1)Prim 算法所需的所有操作。由于堆的时间复杂度会影响主算法的复杂度，因此可以比默认的泛型实现更好。

Answer 3

对于非二进制堆 Prim 的实现，可以在 Cormen, Introduction to Algorithms, 3rd edition 中找到伪代码。

知道范围是 1...k，我们可以创建一个大小为 k 的数组并遍历列表，将边添加到相应的权重。这，就其存储的性质而言，意味着边缘按权重排序。这将是 O(n+m) 时间。

依靠 Cormen 中 Prim 算法的伪代码，我们可以分析其复杂性以得到 O(nlog{n} + mlog{n}) = O((n+m)log{n}) 时间（Cormen 第 636 页）。具体来说，步骤 7 和步骤 11 贡献了在 n 和 m 循环上迭代的 log{n} 元素。n log{n}-loop 来自 EXTRACT-MIN 操作，m log{n}-loop 来自“隐式 DECREASE-KEY”操作。两者都可以用我们的边权数组替换，一个 O(k) 的循环。因此，使用我们修改后的 Prim 算法，我们将有一个 O(nk + mk) = O(k(n+m)) 算法。