我想知道什么时候应该使用整洁的算法，什么时候使用克鲁斯卡来找到最小生成树?它们都有简单的逻辑，同样的最坏情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么呢?
当你有一个有很多边的图时，使用Prim算法。
对于一个具有V顶点E边的图，Kruskal的算法可以在O(E log V)时间内运行，而Prim的算法可以在O(E + V log V)平摊时间内运行，如果你使用斐波那契堆。
当你有一个非常密集的图，边比顶点多的时候，Prim的算法在极限上要快得多。Kruskal在典型情况下(稀疏图)性能更好，因为它使用更简单的数据结构。
如果边可以在线性时间内排序，或者已经排序，Kruskal可以有更好的性能。
如果顶点的边数较多，则Prim更好。
Kruskal's的最佳时间是O(elogv)。对于Prim使用fib堆，我们可以得到O(E+V lgV)。因此，在密集图上，Prim的效果要好得多。
我知道你没有要求这样做，但如果你有更多的处理单元，你应该总是考虑Borůvka的算法，因为它可能很容易并行化——因此它比Kruskal和Jarník-Prim算法有性能优势。
如果我们中途停止算法，prim的算法总是生成连接的树，而kruskal的算法可以给出连接的树或森林
Kruskal算法的一个重要应用是在单链路集群中。
考虑n个顶点，你就有了一个完整的图。得到这n个点组成的k个簇。在已排序边集的前n-(k-1)条边上运行Kruskal算法。你得到了具有最大间距的图的k个簇。
Prim's更适合于更密集的图，在这种情况下，我们也不必通过添加边来关注循环，因为我们主要处理的是节点。在复杂图的情况下，Prim的比Kruskal的更快。
我在网上找到了一个很好的帖子，用一种非常直接的方式解释了区别:http://www.thestudentroom.co.uk/showthread.php?t=232168。
Kruskal的算法将通过添加下一个最便宜的边来从最便宜的边增长一个解，前提是它不创建一个循环。
Prim的算法将通过添加下一个最便宜的顶点来从一个随机顶点增长一个解，这个顶点目前不在解中，但通过最便宜的边连接到它。
这里附上了一份关于这个主题的有趣的表格。
如果你同时实现Kruskal和Prim，以它们的最佳形式:分别使用联合查找和finbonacci堆，那么你会注意到Kruskal与Prim相比是多么容易实现。
Prim使用fibonacci堆比较困难，主要是因为您必须维护一个簿记表来记录图节点和堆节点之间的双向链接。而Union Find则恰恰相反，它的结构很简单，甚至可以直接生成mst，几乎没有额外的成本。
graph like this _____________ | | | | | | |__________| |
给任意顶点a b c d e f命名。
克鲁斯卡尔时间复杂度最坏的情况是O(E log E)，这是因为我们需要对边排序。 整洁的时间复杂度最坏的情况是O(E log V)和优先队列，更好的情况是O(E+V log V)和斐波那契堆。 我们应该使用Kruskal当图是稀疏的，即少量的边，如E=O(V)，当边已经排序或如果我们可以在线性时间内排序。 当图是密集的，即边的数量很高时，我们应该使用Prim，如E=O(V²).
