JavaScriptデータ構造14——図の深さ優先巡回

図が隣接行列で示されている場合、アルゴリズムは以下の通りです.

//        
//          
//  
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;
  this.arc.data[j][i] = length;
}
//    
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 vertexs = [v0,v1,v2,v3,v4];
var mgraph = new Mgraph(5,6,vertexs);
 mgraph.addArc(v1,v0,9);
 mgraph.addArc(v1,v2,3);
 mgraph.addArc(v2,v3,5);
 mgraph.addArc(v3,v4,1);
 mgraph.addArc(v0,v4,6);
 mgraph.addArc(v2,v0,2);
 //console.info(mgraph.arc);

 //    
 Mgraph.prototype.DFS = function(i){
    this.vertexs[i].visited = true;
    console.info(this.vertexs[i]);
    for(var j=0;j0&&this.arc.data[i][j]

出力
Vetex｛name:'V 0',visited:true｝to V 1 Verstex｛name:'V 1',visited:true｝V 0 is visited!トV 2 Vetex{name:'V 2',visited:true}V 0 is visited!V 1 is visitedトV 3 Vetex{name:'V 3',visited:true}V 2 is visited!トV 4 Vetex{name:'V 4',visited:true}V 0 is visited!V 3 is visitedV 2 is visitedV 4 is visited[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);

//    
Graph.prototype.DFS = function(vertex){
  vertex.visited = true;
  console.info(vertex.name);
  var p = vertex.firstEdge;
  while(p){
    if(p.adjVex.visited){
      console.info(p.adjVex.name+' is visited!');
    }
    if(!p.adjVex.visited){
      console.info('to '+p.adjVex.name);
      this.DFS(p.adjVex);
    }
    p = p.next;
  }
}
Graph.prototype.DFSTraverse = function(){
  for (var i = 0; i < this.vertexs.length; i++) {
    this.vertexs[i].visited = false;
  }
  for (var i = 0; i < this.vertexs.length; i++) {
    if(!this.vertexs[i].visited){
      this.DFS(this.vertexs[i]);
    }
  }
}
g.DFSTraverse();

印刷
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'}V0 to V 4 V 1 V 0 is visited!to V 2 V 2 V 0 is visited!to V 3 V 3 V 1 is visited![Finished in 0.1 s]