本站以前有一篇文章提到了 prim 算法的实现，具体点这里，我写了完整的示例，和优化版的 prim 在时间上的对比。现在我们来看另一种思路：Kruskal。
话不多说，先看实际效果和结论。在 1k 个节点里，lazy prim 耗时在 4s 左右，优化后的 prim 在 900ms 左右，而更高效的 Kruskal 在 600ms 左右。测试的前提条件是基于我的电脑硬件配置和 1k 个节点的完全稠密图。
要实现高效的 Kruskal 算法，需要基于高效的并查集数据结构，但是并查集我们不在这篇文章里谈及，我们主要谈谈 Kruskal 的思路。
继续阅读“最小生成树 kruskal 算法 js 实现”