数据结构(十四)之图结构

如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: coderwhy, 或者添加我的微信: 372623326

在计算机程序设计中, 图也是一种非常常见的数据结构.

但是, 图论其实是一个非常大的话题, 我们通过本章的学习来认识一下关于图的一些内容以及图的抽象数据类型.

一. 图的概念

我们先来认识一下什么是图, 另外图中也有很多其他的概念, 比如: 顶点/边/有向图/无向图等等.

什么是图?

• 图是一种与树有些相似的数据结构.

  • 实际上, 在数学的概念上, 树是图的一种.
  • 我们知道树可以用来模拟很多现实的数据结构, 比如: 家谱/公司组织架构等等

• 那么图长什么样子呢? 或者什么样的数据使用图来模拟更合适呢?

  • 人与人之间的关系网.
    • 甚至科学家们在观察人与人之间的关系网时, 还发现了六度空间理论.
  img

  • 互联网中的网络关系

    img

  • 村庄间的关系网

    img

  • 北京地铁图

    img

• 那么, 什么是图呢?

  • 我们会发现, 上面的结点(其实图中叫顶点Vertex)之间的关系, 是不能使用树来表示(几叉树都不可以)
  • 这个时候, 我们就可以使用图来模拟它们.

• 图通常有什么特点呢?

  • 一组顶点：通常用 V (Vertex) 表示顶点的集合
  • 一组边：通常用 E (Edge) 表示边的集合
    • 边是顶点和顶点之间的连线
    • 边可以是有向的, 也可以是无向的.(比如A --- B, 通常表示无向. A --> B, 通常表示有向)

图的术语

• 关于术语

  • 我们在学习树的时候, 树有很多的其他术语, 了解这些术语有助于我们更深层次的理解图.
  • 我们也来学习一下图相关的术语.
  • 但是图的术语其实非常多, 如果你找一本专门讲图的各个方面的书籍, 会发现只是术语就可以占据一个章节.
  • 这里, 我们先介绍几个比较常见的术语, 某些术语后面用到的时候, 再了解. 没有用到的, 在自行深入学习的过程中, 可以通过查资料去了解.

• 我们先来看一个抽象出来的图

  img

• 顶点:

  • 顶点刚才我们已经介绍过了, 表示图中的一个结点.
  • 比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人.

• 边:

  • 边刚才我们也介绍过了, 表示顶点和顶点之间的连线.
  • 比如地铁站中两个站点之间的直接连线, 就是一个边.
  • 注意: 这里的边不要叫做路径, 路径有其他的概念, 待会儿我们会介绍到.
  • 下面的图中: 0 - 1有一条边, 1 - 2有一条边, 0 - 2没有边.

• 相邻顶点

  • 由一条边连接在一起的顶点称为相邻顶点.
  • 比如0 - 1是相邻的, 0 - 3是相邻的. 0 - 2是不相邻的

• 度:

  • 一个顶点的度是相邻顶点的数量.
  • 比如0顶点和其他两个顶点相连, 0顶点的度是2
  • 比如1顶点和其他四个顶点相连, 1顶点的度是4

• 路径:

  • 路径是顶点v1, v2..., vn的一个连续序列, 比如上图中0 1 5 9就是一条路径.
  • 简单路径: 简单路径要求不包含重复的顶点. 比如 0 1 5 9是一条简单路径.
  • 回路: 第一个顶点和最后一个顶点相同的路径称为回路. 比如 0 1 5 6 3 0

• 无向图:

  • 上面的图就是一张无向图, 因为所有的边都没有方向.
  • 比如 0 - 1之间有变, 那么说明这条边可以保证 0 -> 1, 也可以保证 1 -> 0.

• 有向图:

  • 有向图表示的图中的边是有方向的.
  • 比如 0 -> 1, 不能保证一定可以 1 -> 0, 要根据方向来定.

• 无权图和带权图

  • 无权图:
    • 我们上面的图就是一张无权图(边没有携带权重)
    • 我们上面的图中的边是没有任何意义的, 不能收 0 - 1的边, 比4 - 9的边更远或者用的时间更长.
  • 带权图:
    • 带权图表示边有一定的权重.
    • 这里的权重可以是任意你希望表示的数据: 比如距离或者花费的时间或者票价.

• 我们来看一张有向和带权的图

  img

现实建模

• 图可用于对现实中很多系统建模
  • 对交通流量建模
    • 顶点可以表示街道的十字路口, 边可以表示街道.
    • 加权的边可以表示限速或者车道的数量或者街道的距离.
    • 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道.
  • 对飞机航线建模
    • 航空公司可以用图来为其飞行系统建模.
    • 将每个机场看成顶点, 将经过两个顶点的每条航线看作一条边.
    • 加权的边可以表示从一个机场到另一个机场的航班成本, 或两个机场间的距离.
    • 建模人员可以利用这个系统有效的判断从一个城市到另一个城市的最小航行成本.
  • ​

二. 图的表示

怎么在程序中表示图呢?

我们知道一个图包含很多顶点, 另外包含顶点和顶点之间的连线(边), 这两个都是非常重要的图信息, 因此都需要在程序中体现出来.

顶点表示

• 顶点的表示相对简单, 我们先讨论顶点的表示.
  • 上面的顶点, 我们抽象成了1 2 3 4, 也可以抽象成A B C D. 在后面的案例中, 我们使用A B C D.
  • 那么这些A B C D我们可以使用一个数组来存储起来(存储所有的顶点)
  • 当然, A, B, C, D有可能还表示其他含义的数据(比如村庄的名字), 这个时候, 可以另外创建一个数组, 用于存储对应的其他数据.
• 那么边怎么表示呢?
  • 因为边是两个顶点之间的关系, 所以表示起来会稍微麻烦一些.
  • 下面, 我们具体讨论一下变常见的表示方式.

邻接矩阵

• 一种比较常见的表示图的方式: 邻接矩阵.

  • 邻接矩阵让每个节点和一个整数向关联, 该整数作为数组的下标值.
  • 我们用一个二维数组来表示顶点之间的连接.

• 画图演示:

  img

• 图片解析:

  • 在二维数组中, 0表示没有连线, 1表示有连线.
  • 通过二维数组, 我们可以很快的找到一个顶点和哪些顶点有连线.(比如A顶点, 只需要遍历第一行即可)
  • 另外, A - A, B - B(也就是顶点到自己的连线), 通常使用0表示.

• 邻接矩阵的问题:

  • 如果是一个无向图, 邻接矩阵展示出来的二维数组, 其实是一个对称图.
    • 也就是A -> D是1的时候, 对称的位置 D -> 1一定也是1.
    • 那么这种情况下会造成空间的浪费, 你有没有办法可以优化呢? 作为一个思考题, 大家可以自行研究一下(如果有机会视频讲解, 我们会给出答案, 或者后续留言中, 给出答案)
  • 邻接矩阵还有一个比较严重的问题就是如果图是一个稀疏图
    • 那么矩阵中将存在大量的0, 这意味着我们浪费了计算机存储空间来表示根本不存在的边.
    • 而且即使只有一个边, 我们也必须遍历一行来找出这个边, 也浪费很多时间.

邻接表

• 另外一种常用的表示图的方式: 邻接表.

  • 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成.
  • 这个列表有很多中方式来存储: 数组/链表/字典(哈希表)都可以.

• 画图演示:

  img

• 图片解析:

  • 其实图片比较容易理解.
  • 比如我们要表示和A顶点有关联的顶点(边), A和B/C/D有边, 那么我们可以通过A找到对应的数组/链表/字典, 再取出其中的内容就可以啦.

• 邻接表的问题:

  • 邻接表计算"出度"是比较简单的(出度: 指向别人的数量, 入度: 指向自己的数量)
  • 邻接表如果需要计算有向图的"入度", 那么是一件非常麻烦的事情.
  • 它必须构造一个"“逆邻接表", 才能有效的计算"入度". 而临街矩阵会非常简单.

三. 图的封装

我们像封装其他数据结构一样, 来封装一下图.

创建图类

• 我们先来创建Graph类

  function Graph() {
      // 属性
      this.vertexes = [] // 存储顶点
      this.adjList = new Dictionay() // 存储边
      
      // 方法
  }
  

• 代码解析

  • 创建Graph的构造函数, 这个我们在封装其他数据结构的时候已经非常熟悉了.
  • 定义了两个属性:
    • vertexes: 用于存储所有的顶点, 我们说过使用一个数组来保存.
    • adjList: adj是adjoin的缩写, 邻接的意思. adjList用于存储所有的边, 我们这里采用邻接表的形式.
  • 之后, 我们来定义一些方法以及实现一些算法就是一个完整的图类了.

添加方法

• 现在我们来增加一些添加方法.

  • 添加顶点: 可以向图中添加一些顶点.
  • 添加边: 可以指定顶点和顶点之间的边.

• 添加顶点的实现:

  // 添加方法
  Graph.prototype.addVertex = function (v) {
      this.vertexes.push(v)
      this.adjList.set(v, [])
  }
  

• 代码解析:

  • 我们将添加的顶点放入到数组中.
  • 另外, 我们给该顶点创建一个数组[], 该数组用于存储顶点连接的所有的边.(回顾邻接表的实现方式)

• 添加边:

  Graph.prototype.addEdge = function (v, w) {
      this.adjList.get(v).push(w)
      this.adjList.get(w).push(v)
  }
  

• 代码解析:

  • 添加边需要传入两个顶点, 因为边是两个顶点之间的边, 边不可能单独存在.
  • 根据顶点v取出对应的数组, 将w加入到它的数组中.
  • 根据顶点w取出对应的数组, 将v加入到它的数组中.
  • 因为我们这里实现的是无向图, 所以边是可以双向的.

测试代码

• 我们来试验一下上面封装的代码:

  // 测试代码
  var graph = new Graph()
  
  // 添加顶点
  var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
  for (var i = 0; i < myVertexes.length; i++) {
      graph.addVertex(myVertexes[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');
  

• 效果如下:

  img

toString

• 为了能够正确的显示图的结果, 我们来实现一下Graph的toString方法

  Graph.prototype.toString = function () {
      var resultStr = ""
      for (var i = 0; i < this.vertexes.length; i++) {
          resultStr += this.vertexes[i] + "->"
          var adj = this.adjList.get(this.vertexes[i])
          for (var j = 0; j < adj.length; j++) {
              resultStr += adj[j] + " "
          }
          resultStr += "\n"
      }
      return resultStr
  }
  

• 最终结果:

  img