Kruskal算法，克鲁斯卡尔算法的精巧和重心在于，提前将边进行了排序。
//Kruskal算法（需要调用边集数组完成）
//创建边集数组基本列
function Row(begin,end,weight) {
this.begin = begin;
this.end =end;
this.weight = weight;
}
//创建边集数组
function Edges(numV){
this.edges = [];
this.numV = numV;
}
//增加边集数组添加方法
Edges.prototype.addRow = function(row) {
this.edges.push(row);
};
//最小生成树运算方案（克鲁斯卡尔）
Edges.prototype.miniSpanTree_Krukal = function(){
Array.prototype.Find = function(f){
var f;
while(this[f]>0){
f = this[f];
}
return f;
}
var parent =[];
var n,m;
for (var i = 0; i < this.numV; i++) {
parent.push(0);
}
for (var i = 0; i < this.edges.length; i++) {
n = parent.Find(this.edges[i].begin);
m = parent.Find(this.edges[i].end);
if(n!=m){
parent[n] = m;
console.info('('+this.edges[i].begin+','+
this.edges[i].end
+'),'+this.edges[i].weight)
}
}
}
//创建一个边集数组(点直接用数字表示，不创建NODE对象了)!!!边集数组的权值是从小到大排序的
var e = new Edges(9);
e.addRow(new Row(4,7,7));
e.addRow(new Row(2,8,8));
e.addRow(new Row(0,1,10));
e.addRow(new Row(0,5,11));
e.addRow(new Row(1,8,12));
e.addRow(new Row(3,7,16));
e.addRow(new Row(1,6,16));
e.addRow(new Row(5,6,17));
e.addRow(new Row(1,2,18));
e.addRow(new Row(6,7,19));
e.addRow(new Row(3,4,20));
e.addRow(new Row(3,8,21));
e.addRow(new Row(2,3,22));
e.addRow(new Row(3,6,24));
e.addRow(new Row(4,5,26));
console.info(e);
e.miniSpanTree_Krukal();
输出
Edges {
edges:
[ Row { begin: 1, end: 2, weight: 18 },
Row { begin: 4, end: 7, weight: 7 },
Row { begin: 2, end: 8, weight: 8 },
Row { begin: 0, end: 1, weight: 10 },
Row { begin: 0, end: 5, weight: 11 },
Row { begin: 1, end: 8, weight: 12 },
Row { begin: 3, end: 7, weight: 16 },
Row { begin: 1, end: 6, weight: 16 },
Row { begin: 5, end: 6, weight: 17 },
Row { begin: 6, end: 7, weight: 19 },
Row { begin: 3, end: 4, weight: 20 },
Row { begin: 3, end: 8, weight: 21 },
Row { begin: 2, end: 3, weight: 22 },
Row { begin: 3, end: 6, weight: 24 },
Row { begin: 4, end: 5, weight: 26 } ],
numV: 9 }
(1,2),18
(4,7),7
(2,8),8
(0,1),10
(0,5),11
(3,7),16
(1,6),16
(6,7),19
[Finished in 0.1s]
