Kruskal算法，克魯斯卡爾算法的精巧和重心在于朽们，提前將邊進(jìn)行了排序的烁。
//Kruskal算法（需要調(diào)用邊集數(shù)組完成）
//創(chuàng)建邊集數(shù)組基本列
function Row(begin,end,weight) {
this.begin = begin;
this.end =end;
this.weight = weight;
}
//創(chuàng)建邊集數(shù)組
function Edges(numV){
this.edges = [];
this.numV = numV;
}
//增加邊集數(shù)組添加方法
Edges.prototype.addRow = function(row) {
this.edges.push(row);
};
//最小生成樹(shù)運(yùn)算方案（克魯斯卡爾）
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)
}
}
}
//創(chuàng)建一個(gè)邊集數(shù)組(點(diǎn)直接用數(shù)字表示奶镶，不創(chuàng)建NODE對(duì)象了)!!!邊集數(shù)組的權(quán)值是從小到大排序的
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]
