克鲁斯卡尔普利姆 克鲁斯卡尔 算法 哪个更快？

最小生成树除了用普利姆算法，克鲁斯卡尔算法，遗传算法，还可以用什么算法来解决呢？

经典的算法就是普利姆算法和克鲁斯卡尔算法了，像遗传算法、模拟退火、禁忌搜索等元启发式算法，都有点大材小用了，个人不推荐使用这些算法去求最小生成树。

再有其他的算法，也是基于普利姆算法和克鲁斯卡尔算法的基础上，所做的一些改良。

克鲁斯卡尔算法中回路是如何消除的，具体代码是什么？

并查集判断重复的路径 int?root[MAX]; int?getRoot(int?v)?{ ?????if?(v?==?root[v])?return?v; ?????return?root[v]?=?getRoot(root[v]); } void?insert(int?u,?int?v)?{ ????root[getRoot(u)]?=?getRoot(v); }每添加到一条新的边就用insert关联左右的节点。

如果getRoot(u)==getRoot(v)那么u和v有连接

普利姆 克鲁斯卡尔 算法 哪个更快？

在不使用优先队列优化时，普里姆的时间复杂度是O（V ^2) ）的,使用后是O(Elog(V))的。

而快排克鲁斯卡尔是 O（E log (V)）的, 也就是时间复杂度是一样的。

如果你会用费波那契堆，PRIM的效率会有一定的提升。