溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
之前都是看書，大部分也是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;
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
