如何使用 JavaScript 实现图? - 项越资源网-html css js 用法分享社区-开发交流-项越资源网

如何使用 JavaScript 实现图?

/* 如何使用 JavaScript 实现图? */
function Graph() {
  var vertices = [];
  var adjList = new Dictionary();
  this.addVertex = addVertex;
  this.addEdge = addEdge;
  this.toString = toString;
  this.bfs = bfs;
  this.dfs = dfs;
  this.bfsVisit = bfsVisit;
  this.dfsVisit = dfsVisit;
  this.initializeColor = initializeColor;
  function initializeColor() {
    var color = [];
    for (var i = 0; i < vertices.length; i++) {
      color[vertices[i]] = 'white';
    }
    return color;
  }
  function bfs(v, callback) {
    var color = initializeColor(),
      queue = new Queue();
    queue.enqueue(v);
    while (!queue.isEmpty()) {
      var u = queue.dequeue(),
        neighbors = adjList.get(u);
      color[u] = 'grey';
      for (var i = 0; i < neighbors.length; i++) {
        var w = neighbors[i];
        if (color[w] === 'white') {
          color[w] = 'grey';
          queue.enqueue(w);
        }
      }
      color[u] = 'black';
      if (callback) {
        callback(u);
      }
    }
  }
  function dfs(callback) {
    var color = initializeColor();
    for (var i = 0; i < vertices.length; i++) {
      if (color[vertices[i]] === 'white') {
        dfsVisit(vertices[i], color, callback);
      }
    }
  }
  function dfsVisit(u, color, callback) {
    color[u] = 'grey';
    if (callback) {
      callback(u);
    }
    var neighbors = adjList.get(u);
    for (var i = 0; i < neighbors.length; i++) {
      var w = neighbors[i];
      if (color[w] === 'white') {
        dfsVisit(w, color, callback);
      }
    }
    color[u] = 'black';
  }
  function bfsVisit(u, color, callback) {
    color[u] = 'grey';
    var queue = new Queue();
    queue.enqueue(u);
    while (!queue.isEmpty()) {
      var u = queue.dequeue(),
        neighbors = adjList.get(u);
      color[u] = 'grey';
      for (var i = 0; i < neighbors.length; i++) {
        var w = neighbors[i];
        if (color[w] === 'white') {
          color[w] = 'grey';
          queue.enqueue(w);
        }
      }
      color[u] = 'black';
      if (callback) {
        callback(u);
      }
    }
  }
  function addVertex(v) {
    vertices.push(v);
    adjList.set(v, []);
  }
  function addEdge(v, w) {
    adjList.get(v).push(w);
    adjList.get(w).push(v);
  }
  function toString() {
    var s = '';
    for (var i = 0; i < vertices.length; i++) {
      s += vertices[i] + ' -> ';
      var neighbors = adjList.get(vertices[i]);
      for (var j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + ' ';
      }
      s += '\n';
    }
    return s;
  }
}
var graph = new Graph();
var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (var i = 0; i < myVertices.length; i++) {
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('
请登录后发表评论

    没有回复内容