最小生成树 kruskal 算法 js 实现

本站以前有一篇文章提到了 prim 算法的实现，具体点这里，我写了完整的示例，和优化版的 prim 在时间上的对比。现在我们来看另一种思路：Kruskal。

话不多说，先看实际效果和结论。在 1k 个节点里，lazy prim 耗时在 4s 左右，优化后的 prim 在 900ms 左右，而更高效的 Kruskal 在 600ms 左右。测试的前提条件是基于我的电脑硬件配置和 1k 个节点的完全稠密图。

要实现高效的 Kruskal 算法，需要基于高效的并查集数据结构，但是并查集我们不在这篇文章里谈及，我们主要谈谈 Kruskal 的思路。

Kruskal 的思路

1. 找到图中所有的边
2. 将边从小到大排列
3. 选出剩余中最小的边，检测边的两个节点在并查集的根节点是否一致，在的话不选用；否则选用
4. 循环 3 步骤，直到所有边检测完毕

Kruskal 的数学证明就不说了，计算机科学家想出来的东西，理论应该没有问题。

在 codepen 中查看完整代码

我在代码的关键位置写了注释，就不详细描述关键代码了。

See the Pen kruskal with javascript by zeng (@zengxiaoluan) on CodePen.

参考链接

• https://github.com/juzerali/unionfind