之前都是看書，大部分也是c++的實現，但是搞前端不能忘了JS啊，所以JS實現一遍這兩個經典的最小生成樹算法。
一、權重圖和最小生成樹
權重圖：圖的邊帶權重
最小生成樹：在連通圖的所有生成樹中，所有邊的權重和最小的生成樹
本文使用的圖如下：
它的最小生成樹如下：
二、鄰接矩陣
鄰接矩陣：用來表示圖的矩陣就是鄰接矩陣，其中下標表示頂點，矩陣中的值表示邊的權重（或者有無邊，方向等）。
本文在構建鄰接矩陣時，默認Number.MAX_SAFE_INTEGER表示兩個節點之間沒有邊，Number.MIN_SAFE_INTEGER表示當前節點沒有自環。
代碼如下：
/** * 鄰接矩陣 * 值為頂點與頂點之間邊的權值，0表示無自環，一個大數表示無邊(比如10000) * */const MAX_INTEGER = Number.MAX_SAFE_INTEGER;//沒有的邊const MIN_INTEGER = Number.MIN_SAFE_INTEGER;//沒有自環 const matrix= [ [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]];
這個鄰接矩陣表示的圖如下：
三、 邊的表示
一個邊具有權重、起點、重點三個屬性，所以可以創建一個類(對象)，實現如下：
/** * 邊對象 * */function Edge(begin, end, weight) { this.begin = begin; this.end = end; this.weight = weight;} Edge.prototype.getBegin = function () { return this.begin;};Edge.prototype.getEnd = function () { return this.end;};Edge.prototype.getWeight = function () { return this.weight;}; /*class Edge { constructor(begin, end, weight) { this.begin = begin; this.end = end; this.weight = weight; } getBegin() { return this.begin; } getEnd() { return this.end; } getWeight() { return this.weight; }}*/PS：JS這門語言沒有私有變量的說法，這里寫get方法純粹是模擬一下私有變量。可以不用這么寫，可以直接通過屬性訪問到屬性值。
四、Prim算法
將這個算法的文章數不勝數，這里就不細說了。
其大體思路就是：以某頂點為起點，逐步找各頂點上最小權值的相鄰邊構建最小生成樹，同時其鄰接點納入生成樹的頂點中,只要保證頂點不重復添加即可。
實現代碼如下：
/** * Prim算法 * 以某頂點為起點，逐步找各頂點上最小權值的邊構建最小生成樹，同時其鄰接點納入生成樹的頂點中,只要保證頂點不重復添加即可 * 使用鄰接矩陣即可 * 優點：適合點少邊多的情況 * @param matrix 鄰接矩陣 * @return Array 最小生成樹的邊集數組 * */function prim(matrix) { const rows = matrix.length, cols = rows, result = [], savedNode = [0];//已選擇的節點 let minVex = -1, minWeight = MAX_INTEGER; for (let i = 0; i < rows; i++) { let row = savedNode[i], edgeArr = matrix[row]; for (let j = 0; j < cols; j++) { if (edgeArr[j] < minWeight && edgeArr[j] !== MIN_INTEGER) { minWeight = edgeArr[j]; minVex = j; } } //保證所有已保存節點的相鄰邊都遍歷到 if (savedNode.indexOf(minVex) === -1 && i === savedNode.length - 1) { savedNode.push(minVex); result.push(new Edge(row, minVex, minWeight)); //重新在已加入的節點集中找權值最小的邊的外部邊 i = -1; minWeight = MAX_INTEGER; //已加入的邊，去掉，下次就不會選這條邊了 matrix[row][minVex] = MAX_INTEGER; matrix[minVex][row] = MAX_INTEGER; } } return result;}五、Kruskal算法
介紹這個算法的文章也很多，這里不細說。
其主要的思路就是：遍歷所有的邊，按權值從小到大排序，每次選取當前權值最小的邊，只要不構成回環，則加入生成樹。
5.1 鄰接矩陣轉成邊集數組
與Prim算法不同，Kruskal算法是從最小權值的邊開始的，所以使用邊集數組更方便。所以需要將鄰接矩陣轉成邊集數組，并且按照邊的權重從小到大排序。
/** * 鄰接矩陣轉邊集數組的函數 * @param matrix 鄰接矩陣 * @return Array 邊集數組 * */function changeMatrixToEdgeArray(matrix) { const rows = matrix.length, cols = rows, result = []; for (let i = 0; i < rows; i++) { const row = matrix[i]; for(let j = 0 ; j < cols; j++) { if(row[j] !== MIN_INTEGER && row[j] !== MAX_INTEGER) { result.push(new Edge(i, j, row[j])); matrix[i][j] = MAX_INTEGER; matrix[j][i] = MAX_INTEGER; } } } result.sort((a, b) => a.getWeight() - b.getWeight()); return result;}5.2 Kruskal算法的具體實現
Kruskal算法的一個要點就是避免環路，這里采用一個數組來保存已納入生成樹的頂點和邊（連線），其下標是邊（連線）的起點，下標對應的元素值是邊（連線）的終點。下標對應的元素值為0，表示還沒有以它為起點的邊（連線）。
連線：表示一條或多條邊前后連接形成的一條線，這條線沒有環路。
/** * kruskal算法 * 遍歷所有的邊，按權值從小到大排序，每次選取當前權值最小的邊，只要不構成回環，則加入生成樹 * 鄰接矩陣轉換成邊集數組 * 優點：適合點多邊少的情況 * @param matrix 鄰接矩陣 * @return Array 最小生成樹的邊集數組 * */function kruskal(matrix) { const edgeArray = changeMatrixToEdgeArray(matrix), result = [], //使用一個數組保存當前頂點的邊的終點,0表示還沒有已它為起點的邊加入 savedEdge = new Array(matrix.length).fill(0); for (let i = 0, len = edgeArray.length; i < len; i++) { const edge = edgeArray[i]; const n = findEnd(savedEdge, edge.getBegin()); const m = findEnd(savedEdge, edge.getEnd()); console.log(savedEdge, n, m); //不相等表示這條邊沒有與現有生成樹形成環路 if (n !== m) { result.push(edge); //將這條邊的結尾頂點加入數組中，表示頂點已在生成樹中 savedEdge[n] = m; } } return result;} /** * 查找連線頂點的尾部下標 * @param arr 判斷邊與邊是否形成環路的數組 * @param start 連線開始的頂點 * @return Number 連線頂點的尾部下標 * */function findEnd(arr, start) { //就是一直循環，直到找到終點，如果沒有連線，就返回0 while (arr[start] > 0) { start = arr[start]; } return start;}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
