假设您有向图的非负整数边长在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）算法。
我不认为达伦的想法会导致O（m + n + U）时间算法。Jarnik（“ Prim”）不会单调使用其优先级队列，因此可能会多次扫描存储桶。Kruskal需要不交集的数据结构，该结构不能为O（m + n）。
