[已知边缘权重范围时的Prim算法

Question

假设图中的所有边缘权重都是1到| V |范围内的整数。您可以使Prim的算法运行多快？如果对于某些常数W，边缘权重是1到W范围内的整数，该怎么办？

我认为，由于Prim的算法基于最小堆的实现，因此有关边缘权重的知识将无助于加快过程。这是正确的吗？

Answer 1

[具有此约束，您可以实现分别使用O(V) / O(W)空间但具有O(1)插入和O(1) extract-min操作的堆。实际上，对于Prim算法所需的所有操作，您都可以获得O(1)。由于堆的时间复杂度会影响主要算法的复杂度，因此您可以获得比默认泛型实现更好的效果。

Answer 2

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

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

O（V）

建立优先级队列（只需在列表T [W + 1]中插入所有顶点）

O（W）

到提取最小元素（仅移动T搜索第一个非空位置）

O（1）

减小键（如果顶点v的键等于i，并且已更新为j，则只需起飞v从列表T [i]中插入并插入列表T [j]的第一个位置。因此，它将给您带来复杂性

O（VW + E）

而不是O（V logV + E）。（当然，如果范围是1到

V

，它将不起作用，因为V ^ 2 + E大于V \ logV + E。] >>

Answer 3

对于非二进制堆Prim的实现，伪代码可以在Cormen，算法简介，第三版中找到。