JavaScriptデータ構造17——最小生成ツリーKruskyalアルゴリズム

Kruskyalアルゴリズムは、クルースカルアルゴリズムの精巧さと重心があり、前にエッジを並べ替えました.

//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,Roybegit:10,Row,beinhtti,ht:::{begit:5,Rowbegit:5,Row,begit:5,begit:5,Row,ht:5,ht:5,ht:5,Row,Row,httht::::::::::{begit,Row,Row,end:7,weight:16),Row{begin:1,end:6,weight:16},Rowbegin: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,enhhht,3,hhhhhhhhhhhhhhhht,hhhhht,3,Row,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhht::::｛,Row,Row,hhhhhhhhhhhhhhhhhhhh｝,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.1 s]