章节 7 prim 算法
最小生成树
由一副连通加权无向图中一课权值最小的生成树。
prim 实现：
//定义邻接矩阵
let Arr2 = [
[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535],
[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12],
[65535, 65535, 0, 22, 65535, 65535, 65535, 65535, 8],
[65535, 65535, 22, 0, 20, 65535, 65535, 16, 21],
[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535],
[11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],
[65535, 16, 65535, 65535, 65535, 17, 0, 19, 65535],
[65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535],
[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0],
];
// 定义图结构
class Graph {
constructor(numVertextes, numEdges) {
this.vexs = []; //顶点表
this.arc = []; // 邻接矩阵，可看作边表
this.numVertextes = numVertextes; //图中当前的顶点数
this.numEdges = numEdges; //图中当前的边数
//录入顶点信息
for (let i=0; i < this.numVertextes; i++) {
this.vexs[i] = "V" + i;
}
console.log(this.vexs); //打印顶点
//邻接矩阵初始化
for (let i=0; i < this.numVertextes; i++) {
this.arc[i] = [];
for (let j=0; j < this.numVertextes; j++) {
this.arc[i][j] = Arr2[i][j];
}
}
console.log(this.arc); //打印邻接矩阵
}
getMiniSpanTreePrim() {
let min, i, j, k;
let adjvex = []; // 保存相关顶点下标
let lowcost = []; // 保存相关顶点间的权值
for (i = 0; i < this.numVertextes; i++) {
lowcost[i] = this.arc[0][i]; //将V0顶点与之有边的权的权值存入数组
adjvex[i] = 0; //初始化都为v0的下标
}
for (i = 1; i < this.numVertextes; i++) {
min = 65535;
j = 0;
k = 0;
while (j < this.numVertextes) {
//如果权值不为0且小于min
if (lowcost[j] !== 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
j++;
}
lowcost[k] = 0; //将当前顶点的权值设置为0，表示此顶点已完成任务
console.log("(%s, %s, %d)", this.vexs[adjvex[k]], this.vexs[k], min); //打印顶点名称和权值
//循环所有顶点
for (j = 0; j < this.numVertextes; j++) {
//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
if (lowcost[j] !== 0 && this.arc[k][j] < lowcost[j]) {
lowcost[j] = this.arc[k][j]; //将较小权值存入 lowcost
adjvex[j] = k;
}
}
}
}
}
var numVertextes = 9;
var numEdges = 15;
console.log("最小生成树");
var ss = new Graph(numVertextes, numEdges);
ss.getMiniSpanTreePrim();