当边长受限时最小生成树的快速算法？

Question

假设您有一个有向图，其非负整数边长在 0 到 U - 1 范围内（包括 0 和 U - 1）。计算该图的最小生成树最快的算法是什么？我们仍然可以使用现有的最小生成树算法，例如Kruskal算法O(m log n))或Prim算法(O(m + n log n))。然而，对于 U 很小的情况，我认为应该可以做得更好。

是否有任何算法能够与更传统的 MST 算法竞争，能够利用边长度被限制在某个范围内的事实？

谢谢！

Answer 1

Fredman–Willard 针对单位成本 RAM 上的整数边长给出了 O(m + n) 算法。

这可以说并不算太大的改进：在没有边长度限制的情况下（即，长度是一种不透明的数据类型，仅支持比较），Chazelle 给出了 O(m alpha(m, n) + n) 算法（alpha 是反阿克曼函数）和 Karger-Klein-Tarjan 给出了随机 O(m + n) 算法。

我不认为 Darren 的想法会导致 O(m + n + U) 时间算法。 Jarnik（“Prim”）不单调地使用其优先级队列，因此桶可能会被多次扫描； Kruskal 需要一个不相交集的数据结构，它不能是 O(m + n)。

Answer 2

通过整数边权重，您可以使用分桶来实现最坏情况 O(1) 复杂度的优先级队列，但会增加 O(U) 空间复杂度。

在您提到的 MST 算法中，您应该能够用此整数结构替换基于比较的优先级队列，从而消除复杂性要求中的 O(log(n)) 依赖性。我预计您最终会得到 O(n + m) 风格的整体复杂性。

本质上，您设置了一组压缩链接列表，其中每个列表都按与该存储桶关联的（整数！）成本进行索引：

struct bucket_list
{
    _cost; // array[0..N-1] holding current cost for each item

    _head; // array[0..U-1] holding index of first item in each bucket

    _next; // array[0..N-1] where _next[i] is the next item 
           // in a list for the ith item

    _prev; // array[0..N-1] where _prev[i] is the last item 
           // in a list for the ith item
};

此结构基于每个项目只能同时位于单个存储桶列表中的事实。

基于此结构，您可以实现这些操作的最坏情况 O(1) 复杂度：

push(item, cost); // push an item onto the head of the appropriate bucket list

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list

update(item, old_cost, new_cost); // move an item between buckets by combining
                                  // push and _pop

要使用此结构作为优先级队列，您只需维护一个指向当前要扫描的最小存储桶的索引。当您想要获得下一个成本最低的项目时，您只需从该存储桶中弹出头项目即可。如果存储桶为空，则增加存储桶索引，直到找到非空存储桶。

当然，如果U变得非常大，额外的空间复杂度以及项目在存储桶上稀疏分布的可能性可能会使这种方法失去吸引力。