如何用Prim和Kruskal算法在JavaScript中实现最小生成树？

本文共计1602个文字，预计阅读时间需要7分钟。

以前都是看书，大部分也是C++的实现，但搞前端不能忘了JS啊，所以用JS实现了一趟这两个经典的算法：一、权重大小图和最小生成树；权重大小图：图的边权重的排序 + 最小生成树：图的最小生成树

之前都是看书，大部分也是c++的实现，但是搞前端不能忘了JS啊，所以JS实现一遍这两个经典的最小生成树算法。

一、权重图和最小生成树

权重图：图的边带权重

最小生成树：在连通图的所有生成树中，所有边的权重和最小的生成树

本文使用的图如下：

它的最小生成树如下：

二、邻接矩阵

邻接矩阵：用来表示图的矩阵就是邻接矩阵，其中下标表示顶点，矩阵中的值表示边的权重（或者有无边，方向等）。

本文在构建邻接矩阵时，默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边，Number.MIN_SAFE_INTEGER表示当前节点没有自环。