数据结构--图

[lznbuild]

图

可以用邻接矩阵表示，非常浪费内存，添加和删除点很麻烦
也可用邻接表

var Graph = function(){
  // 存储顶点
  var vertices = [];

  // 边
  var adjList = {}

  // 添加顶点
  var addVertex = function(v){
    vertices.push(v)
    adjList[v] = [];
  }


  // 添加边
  var addEdge = function(a,b){
    adjList[a].push(b)
    adjList[b].push(a)
  }

  

  // white 未发现的节点 gray已发现  black已探索
  var initColor=function(){
    var color = {};
    for(var i=0;i<vertices.length;i++){
      color[vertices[i]] = 'white'
    }
    return color 
  }

    // 遍历的广度优先
  this.bfs = function (v,callback){
    var color = initColor();
    var queue = new Queue();
    queue.enqueue(v);

    while(!queue.isEmpty()){
      var now = queue.dequeue;
      var bian = adList[now];
      for(var i=0;i<bian.length;i++){
        var w = bian[i];
        if(color[w] === 'white'){
          // 未发现的全部入列，并且标识为已发现
          color[w] = 'gray';
          queue.enqueue(w)
        }
      }
      color[now] = 'black';
      if(callback){
        callback(now)
      }

    }
  }
  // 使用广度优先查找最短路径,先建立关系
  // d 距离
  //pred 回溯点
   this.BFS = function (v,callback){
    // 遍历的广度优先
    var color = initColor();
    var queue = new Queue();
    queue.enqueue(v);

    var d = {}
    var pred = {}
    for(let i=0;i<vertices.length;i++){
      d[vertices[i]] = 0; //初始化
      pred[vertices[i]]= null 
    }

    while(!queue.isEmpty()){
      var now = queue.dequeue;
      var bian = adList[now];
      for(var i=0;i<bian.length;i++){
        var w = bian[i];
        if(color[w] === 'white'){
          // 未发现的全部入列，并且标识为已发现
          color[w] = 'gray';

          //设置回溯点
          pred[w] = now
          d[w]=d[now]+1

          queue.enqueue(w)
        }
      }
      color[now] = 'black';
      if(callback){
        callback(now)
      }

    }

    return {
      d,
      pred
    }
  }


  var dfsVisite = function(u,color,callback){
    color[u] = 'gray'
    var n = adList[u]
    for(var i=0;i<n.length;i++){
      var w = n[i];
      if(color[w]) == 'while'){
        dfsVisite(w,color,callback)

      }
    }

    color[u] = 'block';
    if(callback){
      callback(u)
    }
  }

  // 遍历的深度优先
  ths.dfs = function(v,callback){
    var color = initColor(); //初始化
    dfsVisite(v, color, callback)
  }

 
}


// 使用
var s=g.BFS('A');

//广度优先算法查找最短路径
var zuiduan = function(form,to){
  var v = to;
  var path = new Stack();
  while(v!==from){
    path.push(v)
    v = s.pred[v]
  }
  path.push(v)
  var str = '';
  while(!path.isEmpty()){
    str += path.pop()+ '-'
  }

  str = str.slice(0,str.length-1)
  return str
}

// 图的遍历：广度优先（队列） 深度优先（递归，栈）