假设图G中的边权在[0,1]上均匀分布，哪种算法prims或Kruskals更快？
我认为这将是kruskals，因为我们可以利用特定的排序算法，因为排序是kruskals算法的瓶颈步骤。
最佳答案
边缘权重的分布无关紧要。
prim s和kruskals的主要区别在于prim的算法在时间上与顶点数的平方成正比，而kruskal的算法在时间上与边数和边数对数的乘积成正比。因此，prim在稠密图上更快，kruskal在稀疏图上更快。
例如，如果有1000个顶点3000条边（稀疏），那么prim将是k1*1000000，kruskal将是k2*24000。但是如果你有1000个顶点和250000条边（密集），那么kruskal将是k2*3100000。