javascript实现prime（普里姆）算法和kruskal（克鲁斯卡尔）算法 -凯发ag旗舰厅登录网址下载

prime算法

prime算法生成最小生成树（minimum cost spanning tree）的一种算法。

prime算法是从指定的顶点开始构建最小生成树。

prime算法思想如下：

从连通图（v,e）中找最小生成树（u，te）：

（1）假设从顶点v0出发开始构造，u={v0}，te={}；

（2）先找权值最小的边（u，v），u属于u，v属于v-u，并且子图不构成环，则u=u并{v}，te=te并（u，v）；

（3）重复（2），直到u=v。

prime算法的时间复杂度是o(n^2)，与边数无关，适合形成稠密的图的最小生成树。

图解如下：

prime算法程序如下：

// 图（无向图）的邻接矩阵// 两个顶点之间没有边的用number.max_value来表示权值var maxvalue = number.max_value;var matrix = [[maxvalue,6,1,5,maxvalue,maxvalue],[6,maxvalue,5,maxvalue,3,maxvalue],[1,5,maxvalue,5,6,4],[5,maxvalue,5,maxvalue,maxvalue,2],[maxvalue,3,6,maxvalue,maxvalue,6],[maxvalue,maxvalue,4,2,6,maxvalue]];// prime算法的主函数function minispantree_prime(index){var k = index;//起点var edges = [];var closedge = initclosedge(index);for(var i = 1; i

kruskal算法

kruskal算法是另一种形成最小生成树的算法。

与prime算法不同，kruskal从权值最小的边开始形成最小生成树。

kruskal算法与边数有关，它的时间复杂度是o(eloge)（e是边数），kruskal算法适合形成稀疏的图的最小生成树。

图解如下：

kruskal算法程序如下：

// kruskal算法的主函数function minispantree_kruskal(){var edgeobj = generateedgeobj(matrix);edgeobj = sortedge_increse(edgeobj);// 辅助数组vset存储着每个顶点所属的子图分量// 这个数组的作用是判断新加入的边是否会形成回路// 在构建最小生成树时会更新// 初始值，vset[i] = ivar vset = [];for(var i = 0; i < matrix.length; i ){vset.push(i);}var edges = [];var m, n;for(i = 0; i < edgeobj.length; i ){m = locate(edgeobj[i].start, vset);n = locate(edgeobj[i].end, vset);// m，n表示边的两个顶点所属的子图分量// m与n相等时，表示新加入的边会形成回路if(m != n){edges.push({start: edgeobj[i].start,end: edgeobj[i].end});vset[m] = n;//更新vset数组}}return edges;}// 根据邻接矩阵形成边对象的数组// 邻接矩阵与prime算法程序中相同// 数组中每一项是对象// 对象中包含start、end以及weight（权重） function generateedgeobj(matrix){var edgeobj = [];for(var i = 0; i < matrix.length; i ){for(var j = 0; j < i; j ){if(matrix[i][j] != maxvalue){edgeobj.push({start: i,end: j,weight: matrix[i][j]});}}}return edgeobj;}// 对generateedgeobj函数生成的数组进行排序// 这里采用的冒泡排序（升序）// 还可以使用其他排序方法function sortedge_increse(edgeobj){for(var i = 0; i < edgeobj.length-1; i ){for(var j = 0; j < edgeobj.length-1-i; j ){if(edgeobj[j].weight > edgeobj[j 1].weight){var temp = edgeobj[j];edgeobj[j] = edgeobj[j 1];edgeobj[j 1] = temp;}}}return edgeobj;}// 根据顶点下标vexindex查找顶点所属的子图分量function locate(vexindex, vset){var temp = vexindexwhile(temp != vset[temp]){temp = vset[temp];}return temp;}// 验证console.log(minispantree_kruskal());

 

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的javascript实现prime（普里姆）算法和kruskal（克鲁斯卡尔）算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。