我想知道什么时候应该使用Prim's algorithm和当Kruskal's找到最小的生成树？它们都具有简单的逻辑，同样最坏的情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么？
当您有一个包含大量边的图时，请使用Prim的算法。
对于具有V顶点E边的图，Kruskal算法在O（E log V）时间运行，而Prim算法可以在O（E + V log V）摊销时间运行，如果使用Fibonacci Heap。
当你有一个比顶点更多的边缘的真密图时，Prim的算法明显更快。 Kruskal在典型情况下（稀疏图）表现更好，因为它使用更简单的数据结构。
在kruskal算法中，我们在给定图上有多个边和顶点数，但是在每个边上我们都有一些值或权重代表我们可以准备一个新的图，它必须不是循环的或者不是从任何一边靠近的例如
像这样的图_____________ | | | | | | | __________ | |为任何顶点a，b，c，d，e，f命名。
我在网上发现了一个非常好的线程，以非常简单的方式解释了差异：http://www.thestudentroom.co.uk/showthread.php?t=232168。
Kruskal的算法将通过添加下一个最便宜的边缘从最便宜的边缘增加解决方案，前提是它不会创建一个循环。
Prim的算法将通过添加下一个最便宜的顶点来增加随机顶点的解决方案，该顶点当前不在解决方案中但通过最便宜的边连接到顶点。
附件是关于该主题的有趣表格。
如果你以最佳形式实现Kruskal和Prim：分别使用union find和finbonacci堆，那么你会注意到与Prim相比，Kruskal如何易于实现。
使用斐波纳契堆的Prim更难，主要是因为您必须维护一个记账表来记录图节点和堆节点之间的双向链接。使用Union Find，相反，结构简单，甚至可以直接生产mst，几乎不需要额外费用。
我知道你没有要求这个，但如果你有更多的处理单元，你应该总是考虑Borůvka's algorithm，因为它可能很容易并行化 - 因此它比Kruskal和Jarník-Prim算法具有性能优势。
如果边缘可以按线性时间排序，或者已经排序，则Kruskal可以获得更好的性能。
如果顶点的边数很高，则Prim更好。
如果我们在mid prim算法中停止算法总是生成连接树，但另一方面kruskal可以给出断开连接的树或森林
Kruskal时间复杂度最差的情况是O（E log E），这是因为我们需要对边缘进行排序。最坏情况下的Prim时间复杂度是具有优先级队列的O（E log V）或者甚至更好，具有Fibonacci Heap的O（E + V log V）。我们应该在图形稀疏时使用Kruskal，即当边缘已经排序或者我们可以在线性时间内对它们进行排序时，边缘的数量很小，例如E = O（V）。当图形密集时，我们应该使用Prim，即边缘数量很高，如E = O（V²）。
Kruskal算法的一个重要应用是单链路聚类。
考虑n个顶点，你有一个完整的图。要获得那些n个点的ak簇。运行Kruskal的算法在有序边集的第一个n-（k-1）边上。你得到图的k-簇最大间距。
Kruskal的最佳时间是O（E logV）。对于Prim使用fib堆，我们可以得到O（E + V lgV）。因此，在密集的图表上，Prim的更好。
对于更密集的图形，Prim更好，在此我们也不必通过添加边缘来关注周期，因为我们主要处理节点。在复杂图形的情况下，Prim比Kruskal更快。