12

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

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

谢谢！

4

2 回答 2

9

Fredman-Willard 给出了一个 O(m + n) 算法，用于计算单位成本 RAM 上的整数边长。

可以说这并没有太大的改进：没有对边长度的限制（即，长度是仅支持比较的不透明数据类型），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)。

于 2012-01-16T18:22:44.683 回答
4

使用整数边缘权重，您可以使用分桶来实现具有最坏情况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变得非常大，则额外的空间复杂度以及桶上项目的稀疏分布的可能性可能会使这种方法没有吸引力。

于 2012-01-16T00:39:09.767 回答