JavaScriptデータ構造13——隣接行列と隣接表

図の表示方法は、隣接マトリクスで図を示すものが多くあります.

//         
//  
function Vertex(name) {
  this.name =name;
}
//    
//maxvex:   
//arcnum:  
function arc(maxvex,arcnum){
  this.maxvex = maxvex;
  this.arcnum = arcnum;
  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,arcnum,vertexs){
  this.arc = new arc(maxvex,arcnum);
  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;
}
//    
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 vertexs = [v1,v2,v3,v4,v5];
var mgraph = new Mgraph(5,6,vertexs);
 mgraph.addArc(v2,v1,9);
 mgraph.addArc(v2,v3,3);
 mgraph.addArc(v3,v4,5);
 mgraph.addArc(v4,v5,1);
 mgraph.addArc(v1,v5,6);
 mgraph.addArc(v3,v1,2);
 console.info(mgraph);
 console.info(mgraph.arc);

印刷
Mgraphh{arc:arc{maxvex:5,arcnum:6,data:[[Object],[Object],[Object],[Object],[Object],vertexs:[Vetex｛name:'V 1],Vetex｛name:',Vetex｛name:'V 2',Vermme:'V 2',Vevername.',Vevername',Vevername',Vevername',Vevername',Vevername',Vevername',Vevername',VeVevername',VeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVeVenum:6,data:[[0,Infinity,Infinity,Infinity,6],[9,0,3,Infinity,Infinity]［2,Infinity,0,5,Infinity］,［Infinity,Infinity,0,1］,［Infinity,Infinity,Infinity,Infinity,Infinity,0］［Finished in 0.1 s］
隣接表の表示方法

//     
//  
function Vertex(name) {
  this.name =name;
}
// 
function EdgeNode(weight,adjVex){
  this.weight = weight;
  this.adjVex = adjVex;
}
// 
function Graph(vertexs){
  this.vertexs = vertexs;
}
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 edge1 = new EdgeNode(6,v4);
var edge2 = new EdgeNode(9,v0);
var edge3 = new EdgeNode(2,v0);
var edge4 = new EdgeNode(4,v1);
var edge5 = new EdgeNode(3,v2);
var edge6 = new EdgeNode(5,v3);
v0.firstEdge = edge1;
v1.firstEdge = edge2;
v2.firstEdge = edge3;
v3.firstEdge = edge4;
edge2.next = edge5;
edge3.next = edge6;
var vertexs = [v0,v1,v2,v3,v4];
var g = new Graph(vertexs);
console.info(g.vertexs);

出力
Vetex｛name:'V 0',firstEdge:EdgeNode{weight:6,adjVex:[Object],Vetex{name:''V 1',fihtEdge:EdgeNode｛weight:9,adjVex:[Object],neddjext,edddjjext,ext,edddddjjjjjjjedddtttttttttttttttttttttttttttttttttttttttttef,ef,ef,edddddddddddddddnext:[Object],Vetex{name:'V 3',firstEdge:EdgeNode{weight:4,adjVex:[Object]],Verstex{name:'V 4'}[Finished in 0.2 s]
クロスリンク表示

//          
//  
function Vertex(name) {
  this.name =name;
}
// 
function EdgeNode(tailVex,headVex){
  this.tailVex = tailVex;
  this.headVex = headVex;
}
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var e1 = new EdgeNode(v0,v3);
var e2 = new EdgeNode(v1,v0);
var e3 = new EdgeNode(v2,v0);
var e4 = new EdgeNode(v1,v2);
var e5 = new EdgeNode(v2,v1);
v0.firstIn = e2;
v0.firseOut = e1;
v1.firstIn = e5;
v1.firseOut = e2;
v2.firstIn = e4;
v2.firseOut = e3;
v3.firstIn = e1;
e2.headLink = e3;
e2.tailLink = e4;
e3.tailLink = e5;
console.info('    V0     ');
console.info(v0.firstIn);

出力
V 0について出力するすべての入力エッジEdgeNode｛tailVex:Vetex｛name:''V 1',firstIn:EdgeNode｛tailVex:[Object],headVex:[Curular],firseOute:[CCCircuular],headVeeeeeeexVex:Vereeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeexx:Verefix:Vex:[Verefidedededededededededededededex]],hehehehehehehehefifififieeeeeeeeeeObject｝,headlink:EdgeNode{tailVex:Verstex{name:'V 2',firstIn:[Object]firseOute:[CCCCCCCCrcuarar],headVex:Vetex{name:''V 0',firstIn:[CCCCCCCCCCrcuar],firseOute:[Object],tailLink:EdgeNode｛tailVex:[Object],headVeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeexx,hedVeeeeeeeeeeeeeeeexx,headVeeeeeeeeeeeeeeeeeeeeeeeeee[ Curcuar],headVex:Verstex{name:'V 2',firstIn:[Curcuar],firseOut:[Object]}[Finished in 0.2 s]