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

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

/**
 * 邊對(duì)象
 * */
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;
  }
}*/

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

/**
 * 鄰接矩陣轉(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;
}

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