JavaScript数据结构15——图的广度优先遍历

用邻接矩阵存储时

//图的广度优先遍历
//用邻接矩阵存储一个图
//顶点
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;
}
//循环队列
function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//头指针
    this.rear = 0;//尾指针
    this.maxSize = maxSize;
}
//长度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //满
        return 1;
    }
    console.info('入队列'+data.name);
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    var data = this.data[this.front];
    console.info('出队列'+data.name);
    this.front = (this.front+1)%this.maxSize;
    return data;
}
//建造一个
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.BFSTraverse = function(){
    //需要使用队列系统辅助完成
    var q = new Queue(this.arc.maxvex);
    for (var i = 0; i < this.arc.maxvex; i++) {
      this.vertexs[i].visited = false;
    }
    for (var i = 0; i < this.arc.maxvex; i++) {
      if(!this.vertexs[i].visited){
        this.vertexs[i].visited = true;
        q.enterQueue(this.vertexs[i]);
        while(q.length()){
          var data = q.deleteQueue();
          i = this.vertexs.indexOf(data);
          for (var j = 0; j <this.arc.maxvex; j++) {
            if(this.arc.data[i][j]>1&&this.arc.data[i][j]<Infinity
              &&!this.vertexs[j].visited){
              this.vertexs[j].visited = true;
              q.enterQueue(this.vertexs[j]);
            }
          }
        }
      }
    }
 }
 mgraph.BFSTraverse();

输出

arc {
maxvex: 5,
arcnum: 6,
data:
[ [ 0, 9, 2, Infinity, 6 ],
[ 9, 0, 3, Infinity, Infinity ],
[ 2, 3, 0, 5, Infinity ],
[ Infinity, Infinity, 5, 0, 1 ],
[ 6, Infinity, Infinity, 1, 0 ] ] }
入队列V0
出队列V0
入队列V1
入队列V2
入队列V4
出队列V1
出队列V2
入队列V3
出队列V4
出队列V3
[Finished in 0.1s]

用邻接表存储的时候

//图的广度优先遍历
//图的邻接表
//顶点
function Vertex(name) {
  this.name =name;
}
//边
function EdgeNode(weight,adjVex){
  this.weight = weight;
  this.adjVex = adjVex;
}
//图
function Graph(vertexs){
  this.vertexs = vertexs;
}
//循环队列
function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//头指针
    this.rear = 0;//尾指针
    this.maxSize = maxSize;
}
//长度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //满
        return 1;
    }
    console.info('入队列'+data.name);
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    var data = this.data[this.front];
    console.info('出队列'+data.name);
    this.front = (this.front+1)%this.maxSize;
    return data;
}
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.BFSTraverse = function(){
  for (var i = 0; i < this.vertexs.length; i++) {
    this.vertexs[i].visited = false;
  }
  var q = new Queue(this.vertexs.length);
  var p;
  for (var i = 0; i < this.vertexs.length; i++) {
    if(!this.vertexs[i].visited){
      this.vertexs[i].visited = true;
      q.enterQueue(this.vertexs[i]);
      while(q.length()){
        q.deleteQueue();
        p = this.vertexs[i].firstEdge;
        while(p){
          if(p.adjVex&&!p.adjVex){
            p.adjVex.visited = true;
            q.enterQueue(p.adjVex);
          }
          p = p.next;
        }
      }
    }
  }
}
g.BFSTraverse();

输出

[ Vertex {
name: 'V0',
firstEdge: EdgeNode { weight: 6, adjVex: [Object] } },
Vertex {
name: 'V1',
firstEdge: EdgeNode { weight: 9, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V2',
firstEdge: EdgeNode { weight: 2, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V3',
firstEdge: EdgeNode { weight: 4, adjVex: [Object] } },
Vertex { name: 'V4' } ]
入队列V0
出队列V0
入队列V1
出队列V1
入队列V2
出队列V2
入队列V3
出队列V3
入队列V4
出队列V4
[Finished in 0.1s]