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

Question

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

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

谢谢!

Answer 1

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)。