设图G中的边权均匀分布在[0,1]上。哪种算法prims和Kruskals更快?我认为会是kruskals，因为我们可以利用特定的排序算法，因为排序是kruskals算法的瓶颈步骤。
这是您必须进行基准测试的内容。您可以使用奇特的数据结构(van Emde Boas树)和排序算法(一些计数排序的变体)来降低这两种算法的理论预期复杂性，使其更接近线性。然而，目前尚不清楚任何此类技巧是否可以提高任一算法的实际性能。提高内存局部性的技巧可能会产生更大的影响。
边权值的分布不重要。
Prims和Kruskals的主要区别在于Prim算法的运行时间与顶点数的平方成正比，而Kruskal算法的运行时间与边数的对数的乘积成正比。因此，Prim’s在密集图上更快，Kruskal’s在稀疏图上更快。
例如，如果你有1000个顶点3000条边(稀疏)，那么Prim将是K1 * 1,000,000, Kruskal将是K2 * 24,000。但是如果你有1000个顶点和250000条边(密集)那么Kruskal就是K2 * 3100000。
更新2正如@David Eisenstat在下面的评论中指出的那样，在O(E)时间内排序的一种更简单的方法是使用|E|桶进行桶排序。区间[0,1]可分为长度为1/|E|的|E|桶，编号为0,1,2…|E|-1，区间内的权值w属于桶号k = floor(|E| w)。每个桶中权值的期望数为O(1)，因此可以用每个大小为O(1)的|E|插入排序来排序，因此这给出了O(E alpha(V))期望时间的Kruskal算法。
注:如@G。Bach指出，以上假设权重和底(|E| w)浮点乘法的比较可以在O(1)时间内完成，这可能需要一定的怀疑暂停。对于非常大的|E|，这两个操作可能仍然有O(lg E)的贡献。
Update正如G. Bach在下面指出的，第一轮0(1)位基数排序之后的bin大小总是ω (E)，所以下面的答案在技术上不能保证在O(E)时间内排序。然而，有可能选择比0 (lg E)小的数字，也许是0 (lg lg E)或0(根号√lg E)?因此，排序所需的预期时间小于O(elge)。
原始回答
这是CLRS中的练习23.2-6。我很确定Kruskal会更快(因此这里的其他答案都是错误的)。权重的分布对有影响;图的密度/稀疏性无关紧要。
普通版本由排序边权值的O(elge)时间支配。当从均匀分布中获得边权时，我们可以对一些常数位数执行基数排序，然后通过进一步的基数排序来修复相邻子数组中的冲突。这是O(E)时间
然后，剩下的就是普通的Kruskal:使用具有并秩和路径压缩的不相交集(如CLRS第23章)，剩下的工作是O(E alpha(V))，其中alpha(V)是逆Ackermann函数，对于任何相同的V值(想象比宇宙中原子大得难以想象的数字)都是<= 4。
因此，对于基数排序，Kruskal是线性O(E)，其概率任意接近于1。
基数排序注意事项:
预期的碰撞次数(即前15位数字相同的边权重)可以通过使用更多的数字来任意减小，但如果位数为O(lg E)，则碰撞次数将为O(1)。当然，这意味着O(E lg E)基数排序，这将破坏目的。然而，我们实际上并不需要完全避免碰撞，只需要限制它们的大小，这样它们就可以在线性时间内固定。
因此，我们可以考虑在一个"四舍五入"中对某个常数位数(如15)进行排序。基数排序，它将权重数组分成具有相同15位的连续子数组(也称为"bin")，然后在下一轮中，使用第二个"四舍五入"对每个子数组的16-30位进行排序;基数排序。
一个正式的证明将涉及与生日悖论类似的计算，但由于碰撞的概率随着使用的额外数字的数量呈指数下降，应该可以使用O(1)"轮"来完成上述排序，这将导致O(E)总排序时间。