链式前向星

[RubyLouvre]

class GraphByComet {
      constructor(vertices, isDirected = false) {
        var n = vertices.length;
        var map = {}, head = [];
        for (var i = 0; i < n; i++) {
          map[vertices[i]] = i;
          head[i] = -1;
        }
        this.isDirected = isDirected
        this.vertices = vertices; //保存所有顶点信息
        this.head = head;
        this.map = map;
        this.ends = []
      }
      insertEdge(from, to, weight) {
        var len = this.ends.length
        this.ends.push({
          to,
          next: this.head[from],
          weight,
        })
        this.head[from] = len
      }
      addEdge(a, b, weight = 1) {
        var from = this.map[a];
        var to = this.map[b];
        this.insertEdge(from, to, weight);
        if (!this.isDirected) {
          this.insertEdge(to, from, weight);
        }
      }
      dfs(cb) {
        var visited = [];
        for (var i = 0; i < this.vertices.length; i++) {
          if (visited[i] === COLOR.WHITE) {
            dfs(this, i, visited, cb);
          }
        }
      }
      bfs(cb) {
        var visited = []
        var ends = this.ends;
        var queue = [0]
        visited[0] = COLOR.GRAY;
        while (queue.length) {
          var index = queue.shift()
          cb(this.vertices[index], index)
          for (var i = this.head[index]; ~i; i = ends[i].next) {
            var j = ends[i].to;//取是某一终点
            if (visited[j] === COLOR.WHITE) {
              visited[j] = COLOR.GRAY
              queue.push(j)
            }
          }
        }
      }
      toString() {
        var ends = this.ends
        var str = '['
        console.log(this)
        for (var u = 0; u < this.head.length; u++) {
          for (var i = this.head[u]; i != -1; i = ends[i].next) {
            str += `{${u}, ${ends[i].to}, ${ends[i].weight}}\n`;
          }
        }
        return str += ']'
      }
    }
    var COLOR = {
      WHITE: void 0,
      GRAY: 1,
      BLACK: -1
    }
    function dfs(graph, index, visited, cb) {
      visited[index] = COLOR.GRAY; //已被访问
      var ends = graph.ends;
      cb(graph.vertices[index], index) //访问顶点
      //循环以index为起点的所有边
      for (var i = graph.head[index]; ~i; i = ends[i].next) {// ~i相当于 i !==-1
        var j = ends[i].to;//取是某一终点
        if (visited[j] === COLOR.WHITE) {
          dfs(graph, j, visited, cb)
        }
      }
      visited[index] = COLOR.BLACK;//它及其所有子树都被访问
    }

    var g = new GraphByComet(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], true);

     g.addEdge('A', 'B')
     g.addEdge('A', 'F')
     g.addEdge('B', 'G')
     g.addEdge('F', 'G')
     g.addEdge('B', 'C')
     g.addEdge('B', 'I')
     g.addEdge('C', 'I')
     g.addEdge('G', 'H')
     g.addEdge('F', 'E')
     g.addEdge('H', 'D')
     g.addEdge('H', 'E')
     g.addEdge('D', 'E')
     g.addEdge('D', 'G')
     g.addEdge('I', 'D')
     g.addEdge('C', 'D')
     g.addEdge('C', 'D')

    g.bfs(function (el, pos) {
      console.log("访问bfs", el, pos)
    });
    console.log('====')
    g.dfs(function (el, pos) {
      console.log("访问dfs", el, pos)
    });