以前看书，大部分都是C实现，但是前端忘不了JS，所以JS又实现了这两个经典的最小生成树算法。

1.加权图和最小生成树

权重图：图的边带权重

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

本文中使用的数字如下：

它的最小生成树如下：

二、邻接矩阵

邻接矩阵：用来表示图的矩阵是邻接矩阵，其中下标表示顶点，矩阵中的值表示边(或边、方向等)的权重。).

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

代码如下：

/* * *邻接矩阵*值为顶点间边的权重，0表示没有自环，大的数表示没有边(如10000)* */const max _ integer=number。max _ safe _ integer//没有边constmin _ integer=number。min _ safe _整数；//没有自环常量矩阵=[[min _ integer，9，2，max _ integer，6]，[9，min _ integer，3，max _ integer，max _ integer]，[2，3，min _ integer，5，max _ integer]，[MAX_INTEGER，max _ integer，5，min _ integer，1]，[6，max _ integer，MAX_INTEGER，1，MIN _ INTEGER]]；这个邻接矩阵表示的图如下：

第三，边缘的表现

一个边有三个属性：权重、起点和强调，所以一个类(对象)可以如下创建和实现：

/* * * edge对象* */函数edge(开始、结束、权重){this。开始=开始；this.end=endthis.weight=重量；} edge . prototype . getbegin=function(){ return this . begin；};edge . prototype . GetEnd=function(){ return this . end；};edge . prototype . getweight=function(){ return this . weight；};/*class Edge {构造函数(开始、结束、权重){ this.begin=beginthis.end=endthis.weight=重量；} GetBegin(){ return this . begin；} GetEnd(){ return this . end；} getWeight(){ return this . weight；}} */ps: js没有私有变量，所以这里的get方法只是模拟私有变量。您不必写这个，但是您可以直接通过属性访问属性值。

4.Prim算法

关于这个算法的文章数不胜数，这里就不细说了。

总的思路是：以一个顶点为起点，逐步在每个顶点上寻找权重最小的邻边，构建最小生成树，只要不重复添加顶点，其邻点就包含在生成树的顶点中。

实现代码如下：

/** * Prim算法*以一个顶点为起点，在每个顶点上逐渐寻找权重最小的边来构建最小生成树，其相邻点包含在生成树的顶点中。只要不重复添加顶点，就可以使用邻接矩阵。优点：适用于点少边多的情况。* @param矩阵邻接矩阵* @返回最小生成树的Array Edge集合数组* */Function Prim(矩阵){const rows=matrix.length，cols=rows，result=[]，saved node=[0]；//所选节点让minvex=-1，minweight=max _ integerfor(设I=0；I行；i ) { let row=savedNode[i]，edge arr=matrix[row]；for(设j=0；j colsj){ if(edge arr[j]minWeight edge arr[j]！==MIN _ INTEGER){ MinWatch=EdgeArr[j]；minVex=j；} }//确保已保存节点的所有相邻边遍历if(已保存节点。(minvex)===-1 I===已保存节点的索引。length-1){保存的节点。push(min vex)；result.push(新的Edge(row，minVex，minWeight))；//再次找到添加节点集中权重最小的边的外边缘I=-1；minWeight=MAX _ INTEGER//去掉添加的边，下次就不选这条边了。矩阵[row][min vex]=max _ integer；矩阵[minVex][row]=MAX _ INTEGER；} }返回结果；} 5.克鲁斯卡尔算法

关于这个算法的文章很多，这里就不细说了。

主要思想是遍历所有边，按照权重从小到大排序，每次选择当前权重最小的边，只要不形成环就加入生成树。

5.1邻接矩阵转换为边集数组

与Prim算法不同，Kruskal算法从权重最小的边开始，因此使用边集数组更方便。因此需要将邻接矩阵转化为边集数组，按照边的权重从小到大排序。

/* * *邻接矩阵到边集数组的函数* @param矩阵邻接矩阵* @返回array边集数组* */函数changematrixtodegaray(matrix){ const rows=matrix . length，cols=rows，result=[]；for(设I=0；I行；I){ const row=matrix[I]；for(设j=0；j colsj ) { if(row[j]！==MIN_INTEGER行[j]！==MAX _ INTEGER){ result . push(new Edge(I，j，row[j])；矩阵[I][j]=MAX _ INTEGER；矩阵[j][I]=MAX _ INTEGER；} } } result.sort((a，b)=a . getweight()-b . getweight())；返回结果；} 5.2 kruskal算法的具体实现

Kruskal算法的一个关键点是避免循环。这里，数组用于保存生成树中包含的顶点和边(链接)。它的下标是边(链接)的起点，它对应的元素值是边(链接)的终点。下标对应的元素值为0，表示没有以其为起点的边(连接线)。

连接：由一条或多条边来回连接而成的线，没有环。

/** * kruskal算法*遍历所有边，按照权重从小到大排序，每次选择当前权重最小的边，只要不形成循环即可。然后在边集数组中加入生成树*邻接矩阵*优点：适用于点和多边形很少的情况* @param矩阵邻接矩阵* @返回最小生成树的array边集数组* */函数kruskal(matrix){ const edge raray=changematrixtodegaray(matrix)，结果=[]，//用一个数组保存当前顶点边的终点，0表示以它为起点的边还没有被添加，保存的边=新数组(matrix。长度)。填充(0)；for(设i=0，len=edgeArray.length我透镜；I){ const edge=EdgeArray[I]；const n=findEnd(savedEdge，edge . GetBegin())；const m=findEnd(savedEdge，edge . GetEnd())；console.log(savedEdge，n，m)；//不等意味着这条边不与现有的生成树形成环路如果(n！==m){ result . push(edge)；//将此边的结束顶点添加到数组中，表示该顶点已被保存生成树中的ge[n]=m；} }返回结果；}/* * *找到连接顶点的尾下标* @param arr判断边是否形成循环数组* @param连接起点的起点顶点* @返回Number连接顶点的尾下标* */函数setted(arr，start){//只要一直循环，直到找到终点。如果没有连接，返回0 while(arr[start]0){ start=arr[start]；}返回开始；}以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。