JavaScript数据结构16——最小生成树PRIM算法

总体思路

1. 建立一个起点（起点树）

• 查找距离起点树最近的点，加入起点树
• 不断加入最近的点，直至加入所有点

//Prim算法
//用邻接矩阵存储一个图
//顶点
function Vertex(name) {
  this.name =name;
}
//邻接矩阵
//maxvex:顶点数
function arc(maxvex){
  this.maxvex = maxvex;
  this.arcnum = 0;
  this.data = new Array(maxvex);
  for (var i = 0; i < this.data.length; i++) {
    this.data[i] = new Array(maxvex);
    for (var j = 0; j < this.data[i].length; j++) {
      this.data[i][j] = Infinity;
      if(i==j){
        this.data[i][j] = 0;
      }
    }
  }
}
//图
function Mgraph(maxvex,vertexs){
  this.arc = new arc(maxvex);
  this.vertexs = vertexs;
}
//添加边,构造无向边
Mgraph.prototype.addArc = function(start,end,length){
  var i = this.vertexs.indexOf(start);
  var j = this.vertexs.indexOf(end);
  this.arc.data[i][j] = length;
  this.arc.data[j][i] = length;
  this.arc.arcnum++;
}
//最小生成树算法,prim
Mgraph.prototype.miniSpanTree_Prim = function(){
  var result = [];
  var min,j,k;
  var adjvex = [];//相关顶点下标
  var lowcost = [];//相关顶点间边的权值
  lowcost[0] = 0;//表示V0已经完成任务
  adjvex[0] = this.vertexs[0];
  for (var i = 1; i < this.arc.maxvex; i++) {
    lowcost[i] = this.arc.data[0][i];
    adjvex[i] = this.vertexs[0];
  }
  console.info('初始化后的lowcost:'+lowcost);
  console.info('初始化后的adjvex:'+JSON.stringify(adjvex));
  for (var i = 1; i < this.arc.maxvex; i++) {
    min = Infinity;
    j=1;k=0;
    while(j<this.arc.maxvex){
      if(lowcost[j]!=0&&lowcost[j]<min){
        min = lowcost[j];
        k=j;
      }
      j++;
    }
    console.info('选择出的边'+'('+JSON.stringify(adjvex[k])+','+
      JSON.stringify(this.vertexs[k])+')');
    result.push('选择出的边'+'('+JSON.stringify(adjvex[k])+','+
      JSON.stringify(this.vertexs[k])+')');
    lowcost[k] = 0;//表示本节点已经完成任务
    console.info('当前的lowcost:'+lowcost+';k='+k);
    for (j = 1; j < this.arc.maxvex; j++) {
      if(lowcost[j]!=0&&this.arc.data[k][j]<lowcost[j]){
        lowcost[j] = this.arc.data[k][j];
        adjvex[j] = this.vertexs[k];
      }
    }
    console.info('清理筛选后的lowcost:'+lowcost+';k='+k);
  }
  return result;
}
//建造一个
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var v5 = new Vertex('V5');
var v6 = new Vertex('V6');
var v7 = new Vertex('V7');
var v8 = new Vertex('V8');
var vertexs = [v0,v1,v2,v3,v4,v5,v6,v7,v8];
var mgraph = new Mgraph(9,vertexs);
mgraph.addArc(v1,v0,10);
mgraph.addArc(v0,v5,11);
mgraph.addArc(v1,v2,18);
mgraph.addArc(v1,v8,12);
mgraph.addArc(v1,v6,16);
mgraph.addArc(v2,v8,8);
mgraph.addArc(v2,v3,22);
mgraph.addArc(v3,v8,21);
mgraph.addArc(v3,v4,20);
mgraph.addArc(v3,v7,16);
mgraph.addArc(v3,v6,24);
mgraph.addArc(v4,v7,7);
mgraph.addArc(v4,v5,26);
mgraph.addArc(v5,v6,17);
console.info(mgraph.arc);
console.info(mgraph.miniSpanTree_Prim());

输出

arc {
maxvex: 9,
arcnum: 0,
data:
[ [ 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, Infinity, Infinity ],
[ Infinity,
Infinity,
Infinity,
16,
7,
Infinity,
Infinity,
0,
Infinity ],
[ Infinity, 12, 8, 21, Infinity, Infinity, Infinity, Infinity, 0 ] ] }
初始化后的lowcost:0,10,Infinity,Infinity,Infinity,11,Infinity,Infinity,Infinity
初始化后的adjvex:[{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"},{"name":"V0"}]
选择出的边({"name":"V0"},{"name":"V1"})
当前的lowcost:0,0,Infinity,Infinity,Infinity,11,Infinity,Infinity,Infinity;k=1
清理筛选后的lowcost:0,0,18,Infinity,Infinity,11,16,Infinity,12;k=1
选择出的边({"name":"V0"},{"name":"V5"})
当前的lowcost:0,0,18,Infinity,Infinity,0,16,Infinity,12;k=5
清理筛选后的lowcost:0,0,18,Infinity,26,0,16,Infinity,12;k=5
选择出的边({"name":"V1"},{"name":"V8"})
当前的lowcost:0,0,18,Infinity,26,0,16,Infinity,0;k=8
清理筛选后的lowcost:0,0,8,21,26,0,16,Infinity,0;k=8
选择出的边({"name":"V8"},{"name":"V2"})
当前的lowcost:0,0,0,21,26,0,16,Infinity,0;k=2
清理筛选后的lowcost:0,0,0,21,26,0,16,Infinity,0;k=2
选择出的边({"name":"V1"},{"name":"V6"})
当前的lowcost:0,0,0,21,26,0,0,Infinity,0;k=6
清理筛选后的lowcost:0,0,0,21,26,0,0,Infinity,0;k=6
选择出的边({"name":"V8"},{"name":"V3"})
当前的lowcost:0,0,0,0,26,0,0,Infinity,0;k=3
清理筛选后的lowcost:0,0,0,0,20,0,0,16,0;k=3
选择出的边({"name":"V3"},{"name":"V7"})
当前的lowcost:0,0,0,0,20,0,0,0,0;k=7
清理筛选后的lowcost:0,0,0,0,7,0,0,0,0;k=7
选择出的边({"name":"V7"},{"name":"V4"})
当前的lowcost:0,0,0,0,0,0,0,0,0;k=4
清理筛选后的lowcost:0,0,0,0,0,0,0,0,0;k=4
[ '选择出的边({"name":"V0"},{"name":"V1"})',
'选择出的边({"name":"V0"},{"name":"V5"})',
'选择出的边({"name":"V1"},{"name":"V8"})',
'选择出的边({"name":"V8"},{"name":"V2"})',
'选择出的边({"name":"V1"},{"name":"V6"})',
'选择出的边({"name":"V8"},{"name":"V3"})',
'选择出的边({"name":"V3"},{"name":"V7"})',
'选择出的边({"name":"V7"},{"name":"V4"})' ]
[Finished in 0.2s]