图与遍历

图

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

图

相邻定点：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);

未完待续。。。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,968评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,601评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,220评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,416评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,425评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,144评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,432评论 3赞 401
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,088评论 0赞 261
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,586评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,783评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,343评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2赞 345