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<matrix.length; i++){//選擇之后的matrix.length-1個頂點k = locate(closedge);edges.push({start: closedge[k].adjvex,end: k});closedge[k].lowcost = 0;//將頂點k加入最小生成樹// 調整closedgefor(var j = 0; j < matrix.length; j++){if(matrix[k][j] < closedge[j].lowcost){//比較新加入的點closedge[j].adjvex = k;closedge[j].lowcost = matrix[k][j]; }}}return edges;}// 初始化closedge輔助數組// closedge數組表示每個不在最小生成樹中的頂點到最小生成樹的最小權值// closedge[i](i可以理解為頂點的下標)是一個對象，對象中有兩對鍵值，分別是adjvex和lowcost。// lowcost表示頂點i到最小生成樹的最短邊的權值，adjvex就表示那個最短邊的另一個頂點，這個頂點一定在最小生成樹中// closedge數組會隨著構造最小生成樹的過程而更新function initClosedge(index){var result = [];for(var i = 0; i < matrix.length; i++){var temp = {};if(i!=index){var temp = {adjvex: index,lowcost: matrix[index][i]};}else{var temp = {adjvex: 0,lowcost: 0};}result.push(temp);}return result;}// closedge更新后// 需要獲取closedge中lowcost最小的值// 然后根據這個值獲取到下一個加入最小生成樹的頂點function locate(closedge){var min = 0;var index = 0;for(var i = 0; i < matrix.length; i++){if(closedge[i].lowcost != 0){min = closedge[i].lowcost;index = i;break;}}for(var i = index + 1; i < closedge.length; i++){if(closedge[i].lowcost !=0 && closedge[i].lowcost < min){min = closedge[i].lowcost;index = i;}}return index;} // 驗證for(var m = 0; m < matrix.length; m++){var result = miniSpanTree_prime(m);console.log(result);}

---

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());

?

總結

以上是生活随笔為你收集整理的JavaScript实现prime（普里姆）算法和kruskal（克鲁斯卡尔）算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。