如何通过JS实现Prim算法与Kruskal算法构建最小生成树？

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

以前都是看书，大部分也是C++的实现，但搞前端不能忘了JS啊，所以用JS实现了一遍这两个经典的最小生成树算法。一、权重大小图和最小生成树：图的大小权重；最小生成树：在连通图中选择权值最小的边，使得所有顶点都在同一个连通分量中。

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

一、权重图和最小生成树

权重图：图的边带权重

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

本文使用的图如下：

它的最小生成树如下：

二、邻接矩阵

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

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