的快速算法最小生成树时，边长被限制？ [英] A fast algorithm for minimum spanning trees when edge lengths are constrained?

问题描述

假设你有向图，是范围为0至U非负整数边长 - 1，包容性。什么是最快的算法计算该图的最小生成树？我们仍然可以使用现有的最小生成树算法，如Kruskal算法0（M日志N））或Prim算法（O（M + N日志N））。但是，对于情况下，U是小的，我觉得应该可以做的更好这一点。

Suppose that you have a directed graph with nonnegative, integer edge lengths that are in the range 0 to U - 1, inclusive. What is the fastest algorithm for computing a minimum spanning tree of this graph? We can still use existing minimum spanning tree algorithms, such as Kruskal's algorithm O(m log n)) or Prim's algorithm (O(m + n log n)). However, for cases where U is small, I think it should be possible to do much better this.

是否存在与更传统的MST算法，它们能够利用的事实是，边缘的长度被约束为在一定范围内的竞争的任何算法

Are there any algorithms that are competitive with more traditional MST algorithms that are able to exploit the fact that the edge lengths are constrained to be in some range?

谢谢！

推荐答案

弗里德曼 - 威拉德发表了O（M + N）算法的单位成本RAM整数边长。

Fredman–Willard gave an O(m + n) algorithm for integer edge lengths on the unit-cost RAM.

这可以说是没有太大的改进：无边缘长度的限制（即长度是只支持比较不透明的数据类型），Chazelle给了一个O（Mα（M，N）+ n）的算法（阿尔法是逆阿克曼功能）以及卡格尔 - 克莱因的Tarjan给了一个随机O（M + N）算法。

That's arguably not much of an improvement: without the restriction on edge lengths (i.e., the lengths are an opaque data type that supports only comparisons), Chazelle gave an O(m alpha(m, n) + n) algorithm (alpha is the inverse Ackermann function) and Karger–Klein–Tarjan gave a randomized O(m + n) algorithm.

我不认为达伦的想法导致了O（M + N + U） - 时间的算法。 Jarnik（的Prim）不使用它的优先级队列单调，所以水桶可被扫描多次;秩需要一个不相交集数据结构，它不可能是O（M + N）。

I don't think Darren's idea leads to a O(m + n + U)-time algorithm. Jarnik ("Prim") does not use its priority queue monotonically, so buckets may be scanned multiple times; Kruskal requires a disjoint-set data structure, which cannot be O(m + n).

这篇关于的快速算法最小生成树时，边长被限制？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！