JS使用Prim算法和Kruskal算法實現(xiàn)最小生成樹

更新時間：2019年01月17日 10:51:53 作者：隨風丶逆風

這篇文章主要為大家詳細介紹了JS使用Prim算法和Kruskal算法實現(xiàn)最小生成樹，具有一定的參考價值，感興趣的小伙伴們可以參考一下

之前都是看書，大部分也是c++的實現(xiàn)，但是搞前端不能忘了JS啊，所以JS實現(xiàn)一遍這兩個經(jīng)典的最小生成樹算法。

一、權(quán)重圖和最小生成樹

權(quán)重圖：圖的邊帶權(quán)重

最小生成樹：在連通圖的所有生成樹中，所有邊的權(quán)重和最小的生成樹

本文使用的圖如下：

它的最小生成樹如下：

二、鄰接矩陣

鄰接矩陣：用來表示圖的矩陣就是鄰接矩陣，其中下標表示頂點，矩陣中的值表示邊的權(quán)重（或者有無邊，方向等）。

本文在構(gòu)建鄰接矩陣時，默認Number.MAX_SAFE_INTEGER表示兩個節(jié)點之間沒有邊，Number.MIN_SAFE_INTEGER表示當前節(jié)點沒有自環(huán)。

代碼如下：

/**
 * 鄰接矩陣
 * 值為頂點與頂點之間邊的權(quán)值，0表示無自環(huán)，一個大數(shù)表示無邊(比如10000)
 * */
const MAX_INTEGER = Number.MAX_SAFE_INTEGER;//沒有的邊
const MIN_INTEGER = Number.MIN_SAFE_INTEGER;//沒有自環(huán)
 
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]
];

這個鄰接矩陣表示的圖如下：

三、邊的表示

一個邊具有權(quán)重、起點、重點三個屬性，所以可以創(chuàng)建一個類(對象)，實現(xiàn)如下：

/**
 * 邊對象
 * */
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算法

將這個算法的文章數(shù)不勝數(shù)，這里就不細說了。

其大體思路就是：以某頂點為起點，逐步找各頂點上最小權(quán)值的相鄰邊構(gòu)建最小生成樹，同時其鄰接點納入生成樹的頂點中,只要保證頂點不重復(fù)添加即可。

實現(xiàn)代碼如下：

/**
 * Prim算法
 * 以某頂點為起點，逐步找各頂點上最小權(quán)值的邊構(gòu)建最小生成樹，同時其鄰接點納入生成樹的頂點中,只要保證頂點不重復(fù)添加即可
 * 使用鄰接矩陣即可
 * 優(yōu)點：適合點少邊多的情況
 * @param matrix 鄰接矩陣
 * @return Array 最小生成樹的邊集數(shù)組
 * */
function prim(matrix) {
  const rows = matrix.length,
    cols = rows,
    result = [],
    savedNode = [0];//已選擇的節(jié)點
  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;
      }
    }
 
    //保證所有已保存節(jié)點的相鄰邊都遍歷到
    if (savedNode.indexOf(minVex) === -1 && i === savedNode.length - 1) {
      savedNode.push(minVex);
      result.push(new Edge(row, minVex, minWeight));
 
      //重新在已加入的節(jié)點集中找權(quán)值最小的邊的外部邊
      i = -1;
      minWeight = MAX_INTEGER;
 
      //已加入的邊，去掉，下次就不會選這條邊了
      matrix[row][minVex] = MAX_INTEGER;
      matrix[minVex][row] = MAX_INTEGER;
    }
  }
  return result;
}

五、Kruskal算法

介紹這個算法的文章也很多，這里不細說。

其主要的思路就是：遍歷所有的邊，按權(quán)值從小到大排序，每次選取當前權(quán)值最小的邊，只要不構(gòu)成回環(huán)，則加入生成樹。

5.1 鄰接矩陣轉(zhuǎn)成邊集數(shù)組

與Prim算法不同，Kruskal算法是從最小權(quán)值的邊開始的，所以使用邊集數(shù)組更方便。所以需要將鄰接矩陣轉(zhuǎn)成邊集數(shù)組，并且按照邊的權(quán)重從小到大排序。

/**
 * 鄰接矩陣轉(zhuǎn)邊集數(shù)組的函數(shù)
 * @param matrix 鄰接矩陣
 * @return Array 邊集數(shù)組
 * */
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算法的具體實現(xiàn)

Kruskal算法的一個要點就是避免環(huán)路，這里采用一個數(shù)組來保存已納入生成樹的頂點和邊（連線），其下標是邊（連線）的起點，下標對應(yīng)的元素值是邊（連線）的終點。下標對應(yīng)的元素值為0，表示還沒有以它為起點的邊（連線）。

連線：表示一條或多條邊前后連接形成的一條線，這條線沒有環(huán)路。

/**
 * kruskal算法
 * 遍歷所有的邊，按權(quán)值從小到大排序，每次選取當前權(quán)值最小的邊，只要不構(gòu)成回環(huán)，則加入生成樹
 * 鄰接矩陣轉(zhuǎn)換成邊集數(shù)組
 * 優(yōu)點：適合點多邊少的情況
 * @param matrix 鄰接矩陣
 * @return Array 最小生成樹的邊集數(shù)組
 * */
function kruskal(matrix) {
  const edgeArray = changeMatrixToEdgeArray(matrix),
    result = [],
    //使用一個數(shù)組保存當前頂點的邊的終點,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);
    //不相等表示這條邊沒有與現(xiàn)有生成樹形成環(huán)路
    if (n !== m) {
      result.push(edge);
      //將這條邊的結(jié)尾頂點加入數(shù)組中，表示頂點已在生成樹中
      savedEdge[n] = m;
    }
  }
  return result;
}
 
/**
 * 查找連線頂點的尾部下標
 * @param arr 判斷邊與邊是否形成環(huán)路的數(shù)組
 * @param start 連線開始的頂點
 * @return Number 連線頂點的尾部下標
 * */
function findEnd(arr, start) {
  //就是一直循環(huán)，直到找到終點，如果沒有連線，就返回0
  while (arr[start] > 0) {
    start = arr[start];
  }
  return start;
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: