最近在看《大話數(shù)據(jù)結(jié)構(gòu)》，圖的算法。書(shū)中用C語(yǔ)言講解的，下面用JavaScript實(shí)現(xiàn)普林姆(prim)算法和克魯斯卡爾(kruskal)算法求解連通網(wǎng)的最小生成樹(shù)

• 普林姆(prim)算法

// 普林姆算法尋找連通網(wǎng)的最小生成樹(shù)
const _ = require('lodash')
// 圖的鄰接矩陣
const G_0 = [
  [0, 10, Infinity, Infinity, Infinity, 11, Infinity, Infinity, Infinity],
  [10, 0, 18, Infinity, Infinity, Infinity, 16, Infinity, 12],
  [Infinity, 18, 0, 22, Infinity, Infinity, Infinity, Infinity, 8],
  [Infinity, Infinity, 22, 0, 20, Infinity, 24, 16, 21],
  [Infinity, Infinity, Infinity, 20, 0, 26, Infinity, 7, Infinity],
  [11, Infinity, Infinity, Infinity, 26, 0, 17, Infinity, Infinity],
  [Infinity, 16, Infinity, 24, Infinity, 17, 0, 19, Infinity],
  [Infinity, Infinity, Infinity, 16, 7, Infinity, 19, 0, Infinity],
  [Infinity, 12, 8, 21, Infinity, Infinity, Infinity, Infinity, 0],
]

function prim(G) {
  'use strict'
  // 初始化: 從下標(biāo)為0的頂點(diǎn)開(kāi)始計(jì)算, lowcost存入0到其他頂點(diǎn)的權(quán)重
  let lowcost = G[0], len = G.length, adjvex = _.times(len, () => 0)
  for (let i = 1; i < len; i++) {
    let min = Infinity, j = 1, k = 0
    while (j < len) {
      // 尋找當(dāng)前頂點(diǎn)到未加入生成樹(shù)頂點(diǎn)中的最小權(quán)重
      if (lowcost[j] != 0 && lowcost[j] < min) {
        min = lowcost[j]
        k = j
      }
      j++
    }
    // 打印當(dāng)前尋到的最小邊
    console.log(adjvex[k], k)
    // 設(shè)置第k個(gè)點(diǎn)為已加入生成樹(shù)
    lowcost[k] = 0

    // 比較第k個(gè)點(diǎn)到其他未加入生成樹(shù)頂點(diǎn)的權(quán)重與之前已加入頂點(diǎn)到所有點(diǎn)的權(quán)重
    for (let m = 1; m < len; m++) {
      if (lowcost[m] != 0 && G[k][m] < lowcost[m]){

        lowcost[m] = G[k][m]
        adjvex[m] = k

      }
    }
  }
}

prim(G_0)

• 克魯斯卡爾(kruskal)算法

/**
 * Created by janeluck on 17/7/11.
 */
// 克魯斯卡爾算法尋找連通網(wǎng)的最小生成樹(shù)
const _ = require('lodash')
// 圖的鄰接矩陣
const G_0 = [
  [0, 10, Infinity, Infinity, Infinity, 11, Infinity, Infinity, Infinity],
  [10, 0, 18, Infinity, Infinity, Infinity, 16, Infinity, 12],
  [Infinity, 18, 0, 22, Infinity, Infinity, Infinity, Infinity, 8],
  [Infinity, Infinity, 22, 0, 20, Infinity, 24, 16, 21],
  [Infinity, Infinity, Infinity, 20, 0, 26, Infinity, 7, Infinity],
  [11, Infinity, Infinity, Infinity, 26, 0, 17, Infinity, Infinity],
  [Infinity, 16, Infinity, 24, Infinity, 17, 0, 19, Infinity],
  [Infinity, Infinity, Infinity, 16, 7, Infinity, 19, 0, Infinity],
  [Infinity, 12, 8, 21, Infinity, Infinity, Infinity, Infinity, 0],
]
// 生成權(quán)值從小到大的邊集數(shù)組
function generateEdge(G) {
  'use strict'
  let edge = [], len = G.length
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      // 排除不存在的邊
      if (G[i][j] !== Infinity) {
        edge.push({
          'begin': i,
          'end': j,
          'weight': G[i][j]
        })
      }
    }
  }
  return _.sortBy(edge, 'weight')
}
function kruskal(G) {
  'use strict'
  const edge = generateEdge(G), find = function (parent, f) {
    while (parent[f] > 0) {
      f = parent[f]
    }
    return f
  }
  let parent = _.times(G.length, () => 0)
  for (let i = 0; i < edge.length; i++) {
    const n = find(parent, edge[i]['begin']), m = find(parent, edge[i]['end'])

    // n與m不等, 索命此邊沒(méi)有與現(xiàn)有生成樹(shù)形成環(huán)路
    if (n !== m) {
      // 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為該起點(diǎn)的parant中
      parent[n] = m
      // 打印當(dāng)前尋到的最小邊
      console.log(edge[i])
    }
  }
}
kruskal(G_0)