连通图求解最小生成树的普林姆(prim)算法和克鲁斯卡尔(kru

最近在看《大话数据结构》，图的算法。书中用C语言讲解的，下面用JavaScript实现普林姆(prim)算法和克鲁斯卡尔(kruskal)算法求解连通网的最小生成树

• 普林姆(prim)算法

// 普林姆算法寻找连通网的最小生成树
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'
  // 初始化: 从下标为0的顶点开始计算, lowcost存入0到其他顶点的权重
  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) {
      // 寻找当前顶点到未加入生成树顶点中的最小权重
      if (lowcost[j] != 0 && lowcost[j] < min) {
        min = lowcost[j]
        k = j
      }
      j++
    }
    // 打印当前寻到的最小边
    console.log(adjvex[k], k)
    // 设置第k个点为已加入生成树
    lowcost[k] = 0

    // 比较第k个点到其他未加入生成树顶点的权重与之前已加入顶点到所有点的权重
    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.
 */
// 克鲁斯卡尔算法寻找连通网的最小生成树
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 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不等, 索命此边没有与现有生成树形成环路
    if (n !== m) {
      // 将此边的结尾顶点放入下标为该起点的parant中
      parent[n] = m
      // 打印当前寻到的最小边
      console.log(edge[i])
    }
  }
}
kruskal(G_0)