图与遍历

作者: kim_jin | 来源:发表于2019-11-01 11:52 被阅读0次

图

图：图是一组由边组成的节点

图

相邻定点：AB是相邻的，AD是相邻的，AC是相邻的，但是AE不是相邻的
路径：是顶点AB...C的一个连续序列，其中AB是相邻的，上图的的路径包括：ABEI
简单路径：要求不包含重复的顶点，举个例子ADG就是一个简单的路径

图的表示

邻接矩阵

这部分的表示就是用二维数组进行表示，如果a[i][j]之间为一，就表示二者之间是有路径的,上图的邻接矩阵是：

邻接矩阵

邻接表

邻接表由每个顶点的相邻顶点的列表所组成,下面的表示方式是邻接表的表示方式

邻接表

关联矩阵

在关联矩阵中，矩阵的行表示顶点，列表示边，我们使用二维数组来表示二者的连通性，如果顶点v是边e的入射点，那么a[v][e] =1,否则就等于0

这种场景我们很少会用到，不详细说明

创建Graph类

我们先创建一个图的数据结构Graph，这个数据结构包含顶点(vertices)和边(adjList ),顶点采用简单的数组结构，边采用Map的数据结构
我们先将所有的顶点添加到我们的图的顶点中，并在这个时候，对顶点的边设置一下对应的值，方便我们后续通过key值来进行查找
我们一次将边放进来，如果是无向图，我们就需要分别放进来，否则，放一次就可以

      function Graph() {
        var vertices = [];
        var adjList = new Map();
       // 添加节点
        this.addVertex = function(v) {
          vertices.push(v);
          adjList.set(v, []);
        };
     // 添加边
        this.addEdge = function(v, w) {
          adjList.get(v).push(w);
          adjList.get(w).push(v);
        };
      // 以合适的方式打印出图
        this.toString = function() {
          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 (let i = 0; i < myVertices.length; i++) {
        graph.addVertex(myVertices[i]);
      }
      graph.addEdge("A", "B");
      graph.addEdge("A", "C");
      graph.addEdge("A", "D");
      graph.addEdge("C", "D");
      graph.addEdge("C", "G");
      graph.addEdge("D", "G");
      graph.addEdge("D", "H");
      graph.addEdge("B", "E");
      graph.addEdge("B", "F");
      graph.addEdge("E", "I");

      console.log(graph.toString());

广度优先遍历（队列）

还是上面的图结构，我们如果进行广度优先遍历的话，节点的顺序应该是：A,B,C,D,E,F,G,H,I
先从理论上分析一下我们应该如何进行遍历：

创建一个队列Q
将v从白色变成灰色，并将v进队列
如果Q非空，运行下面的步骤
- 将u从队列中移除
- 将u变成灰色
- 将u所有违背访问的相邻节点入队列
- 将u标为黑色

   function Graph() {
        var vertices = [];
        var adjList = new Map();
        this.addVertex = function(v) {
          vertices.push(v);
          adjList.set(v, []);
        };
        this.addEdge = function(v, w) {
          adjList.get(v).push(w);
          adjList.get(w).push(v);
        };
        this.toString = function() {
          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;
        };

        this.bfs = function(v, callback) {
          var color = initialzeColor();
          var queue = [];
          queue.push(v);

          while (queue.length > 0) {
            var u = queue.unshift();
            neighbors = adjList.get(u);
            color[u] = "grey";
            for (let i = 0; i < neighbors.length; i++) {
              var w = neighbors[i];
              if (color[w] === "white") {
                color[w] = "grey";
                queue.push(w);
              }
            }
            color[u] = "black";
            if (callback) {
              callback(u);
            }
          }
        };
      }

      // 构造图
      var graph = new Graph();
      var myVertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
      for (let i = 0; i < myVertices.length; i++) {
        graph.addVertex(myVertices[i]);
      }
      graph.addEdge("A", "B");
      graph.addEdge("A", "C");
      graph.addEdge("A", "D");
      graph.addEdge("C", "D");
      graph.addEdge("C", "G");
      graph.addEdge("D", "G");
      graph.addEdge("D", "H");
      graph.addEdge("B", "E");
      graph.addEdge("B", "F");
      graph.addEdge("E", "I");

      console.log(graph.toString());

      // 广度优先搜索

      const initialzeColor = function() {
        var color = [];
        for (var i = 0; i < myVertices.length; i++) {
          color[myVertices[i]] = "white";
        }
        return color;
      };

      function prinNode(value) {
        console.log("当前的节点：", value);
      }
      graph.bfs(myVertices, prinNode);

那我们现在觉得只是单纯的遍历这个值是没有任何意义的，那么我们就想可不可以让这个应用有一点点的实用性

使用BFS实现最短路径

我们的计算方式是，我们添加了两个变量，d和pred用来记录各个节点与初始节点的长度，以及各个节点的回溯节点，我们计算距离的方式是依靠层的关系，每添加一层，节点的距离就会加一。

        this.BFS = function(v, callback) {
          var color = initialzeColor();
          var queue = [];
          var d = []; // 记录距离
          var pred = []; // 前溯节点
          queue.push(v);

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

          while (queue.length > 0) {
            var u = queue.shift();
            var neighbors = adjList.get(u);
            color[u] = "grey";
            for (let i = 0; i < neighbors.length; i++) {
              var w = neighbors[i];
              if (color[w] === "white") {
                color[w] = "grey";
                d[w] = d[u] + 1;//1
                pred[w] = u; //1
                queue.push(w);
              }
            }
            color[u] = "black";
          }
          return { //1
            distance: d,
            predecessors: pred
          };
        };
 var short = graph.BFS(myVertices[0]);
 console.log(short);

还是根据上图的结果进行打出结果为

最短路径的结果

我们先要看各个节点与A节点的关系，我们可以通过回溯，打出路径

 var short = graph.BFS(myVertices[0]);

      for (let i = 0; i < myVertices.length; i++) {
        var toVertex = myVertices[i];
        var path = [];
        for (let v = toVertex; v != "A"; v = short.predecessors[v]) {
          path.push(v);
        }
        path.push("A");
        var s = path.pop();
        while (path.length > 0) {
          s += "-" + path.pop();
        }
        console.log(s);
      }

打印的结果为：

节点的路径

但是我们发现了，这样的最短路径并不适合如果路径加权或是路径不相等的情况，如果我们希望能够找到复杂情况的最短路径，我们需要使用深度遍历的方法啦

总的代码

      function Graph() {
        var vertices = [];
        var adjList = new Map();
        this.addVertex = function(v) {
          vertices.push(v);
          adjList.set(v, []);
        };
        this.addEdge = function(v, w) {
          adjList.get(v).push(w);
          adjList.get(w).push(v);
        };
        this.toString = function() {
          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;
        };

        this.bfs = function(v, callback) {
          var color = initialzeColor();
          var queue = [];
          queue.push(v);
          while (queue.length > 0) {
            var u = queue.shift();
            var neighbors = adjList.get(u);
            color[u] = "grey";
            for (let i = 0; i < neighbors.length; i++) {
              var w = neighbors[i];
              if (color[w] === "white") {
                color[w] = "grey";
                queue.push(w);
              }
            }
            color[u] = "black";
            if (callback) {
              callback(u);
            }
          }
        };

        this.BFS = function(v, callback) {
          var color = initialzeColor();
          var queue = [];
          var d = []; // 记录距离
          var pred = []; // 前溯节点
          queue.push(v);

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

          while (queue.length > 0) {
            var u = queue.shift();
            var neighbors = adjList.get(u);
            color[u] = "grey";
            for (let i = 0; i < neighbors.length; i++) {
              var w = neighbors[i];
              if (color[w] === "white") {
                color[w] = "grey";
                d[w] = d[u] + 1;
                pred[w] = u;
                queue.push(w);
              }
            }
            color[u] = "black";
          }
          return {
            distance: d,
            predecessors: pred
          };
        };
      }

      // 构造图
      var graph = new Graph();
      var myVertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
      for (let i = 0; i < myVertices.length; i++) {
        graph.addVertex(myVertices[i]);
      }
      graph.addEdge("A", "B");
      graph.addEdge("A", "C");
      graph.addEdge("A", "D");
      graph.addEdge("C", "D");
      graph.addEdge("C", "G");
      graph.addEdge("D", "G");
      graph.addEdge("D", "H");
      graph.addEdge("B", "E");
      graph.addEdge("B", "F");
      graph.addEdge("E", "I");

      // console.log(graph.toString());

      // 广度优先搜索

      const initialzeColor = function() {
        var color = [];
        for (var i = 0; i < myVertices.length; i++) {
          color[myVertices[i]] = "white";
        }
        return color;
      };

      function prinNode(value) {
        // console.log("visited Node is", value);
      }
      graph.bfs("A", prinNode);
      var short = graph.BFS(myVertices[0]);

      for (let i = 0; i < myVertices.length; i++) {
        var toVertex = myVertices[i];
        var path = [];
        for (let v = toVertex; v != "A"; v = short.predecessors[v]) {
          path.push(v);
        }
        path.push("A");
        var s = path.pop();
        while (path.length > 0) {
          s += "-" + path.pop();
        }
        console.log(s);
      }
      console.log(short);

未完待续。。。

图与遍历

图

图的表示

邻接矩阵

邻接表

关联矩阵

创建Graph类

广度优先遍历（队列）

使用BFS实现最短路径

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读