我在想什么时候应该用Prim的算法，什么时候用Kruskal的算法来寻找最小生成树?它们都有简单的逻辑，同样的最坏情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么呢?
当前回答
如果边可以在线性时间内排序，或者已经排序，Kruskal可以有更好的性能。
如果顶点的边数较多，则Prim更好。
其他回答
Prim's更适合于更密集的图，在这种情况下，我们也不必通过添加边来关注循环，因为我们主要处理的是节点。在复杂图的情况下，Prim的比Kruskal的更快。
Kruskal's的最佳时间是O(elogv)。对于Prim使用fib堆，我们可以得到O(E+V lgV)。因此，在密集图上，Prim的效果要好得多。
如果边可以在线性时间内排序，或者已经排序，Kruskal可以有更好的性能。
如果顶点的边数较多，则Prim更好。
Kruskal算法的一个重要应用是单链聚类。
考虑n个顶点，你就有了一个完整的图。得到这n个点组成的k个簇。在已排序边集的前n-(k-1)条边上运行Kruskal算法。你得到了具有最大间距的图的k个簇。
当你有一个有很多边的图时，使用Prim算法。
对于具有V个顶点E条边的图，如果使用Fibonacci堆，Kruskal的算法可以在O(E log V)时间内运行，而Prim的算法可以在O(E + V log V)平摊时间内运行。
当你有一个非常密集的图，边比顶点多的时候，Prim的算法在极限上要快得多。Kruskal在典型情况下(稀疏图)性能更好，因为它使用更简单的数据结构。
