tem*_*def 11 algorithm integer minimum-spanning-tree
假设您有一个非负整数边长的有向图,其范围在0到U-1之间.计算此图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法,例如Kruskal算法O(m log n))或Prim算法(O(m + n log n)).但是,对于U很小的情况,我认为应该可以做得更好.
是否存在与更传统的MST算法竞争的算法,这些算法能够利用边长被约束在某个范围内的事实？
谢谢!
小智 8
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).