假设您有一个非负整数边长的有向图，其范围在0到U-1之间（包括0和U-1）。计算此图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法，例如Kruskal算法O（m log n））或Prim算法（O（m + n log n））。但是，对于U很小的情况，我认为应该可以做得更好。
是否存在与更传统的MST算法竞争的算法，这些算法能够利用边长被约束在某个范围内的事实？
谢谢！
假设您有一个非负整数边长的有向图，其范围在0到U-1之间（包括0和U-1）。计算此图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法，例如Kruskal算法O（m log n））或Prim算法（O（m + n log n））。但是，对于U很小的情况，我认为应该可以做得更好。
是否存在与更传统的MST算法竞争的算法，这些算法能够利用边长被约束在某个范围内的事实？
谢谢！
Fredman-Willard在单位成本RAM上给出了整数边长的O（m + n）算法。
这可以说是没有太大的改进：没有边长的限制（即，长度是仅支持比较的不透明数据类型），Chazelle给出了O（m alpha（m，n）+ n）算法（alpha是逆Ackermann函数）和Karger-Klein-Tarjan给出了随机O（m + n）算法。
我认为Darren的想法不会导致O（m + n + U）时间算法。 Jarnik（“Prim”）不单调使用其优先级队列，因此可以多次扫描桶; Kruskal需要一个不相交的数据结构，它不能是O（m + n）。
使用整数边权重，您可以使用bucketing来实现最坏情况下的优先级队列 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 额外的空间复杂度变得非常大，并且在桶上稀疏分布项目的可能性可能使这种方法没有吸引力。