LynDocs

外观

图结构 ​

认识图结构 ​

图结构特点 ​

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

  • 但是，图论 其实是一个非常大的话题

什么是图？

  • 图结构是一种与树结构有些相似的数据结构
  • 图论是数学的一个分支，并且，在数学的概念上，树是图的一种
  • 它以图为研究对象，研究顶点和边组成的图形的数学理论和方法
  • 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系

六度空间理论

  • 理论上认为世界上任何两个互相不认识的两人
  • 只需要很少的中间人就可以建立起联系
  • 并非一定要经过 6 步，只是需要很少的步骤

图结构特点

一组顶点：通常用 V(Vertex) 表示顶点的集合

一组边：通常用 E(Edge) 表示边的集合

  • 边是顶点和顶点之间的连线
  • 边可以是有向的，也可以是无向的
  • 比如 A --- B，通常表示无向。A --> B，通常表示有向

图结构起源 ​

【科普】图论之父欧拉与七桥问题

18 世纪著名古典数学问题之一

  • 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来
  • 有人提出问题: 一个人怎样才能不重复、不遗漏地一次走完七座桥最后回到出发点。

img

1735 年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的瑞典天才数学家欧拉，请他帮忙解决这一问题

  • 欧拉在亲自观察了哥伦斯堡的七桥后，认真思考走法，但是始终没有成功，于是他怀疑七桥问题是不是无解的
  • 1736 年 29 岁的欧拉向 彼得斯堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支一-图论与几何拓扑，也由此展开了数学史上的新历程

他不仅解决了该问题，并且给出了连通图可以一笔画的充要条件是:

  • 奇点的数目不是 0 个就是 2 个
  • 连到一点的边的数目如果是奇数条，就称为奇点
  • 如果是偶数条就称为偶点
  • 要想一笔画成，必须中间点均是偶点口 也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端

个人思考：

  • 欧拉在思考这个问题的时候，并不是针对某一个特性的问题去考虑而是将岛和桥抽象成了点和线
  • 抽象是数学的本质，而编程我们也一再强调抽象的重要性
  • 汇编语言是对机器语言的抽象，高级语言是对汇编语言的抽象
  • 操作系统是对硬件的抽象，应用程序在操作系统的基础上构建

图结构术语 ​

因为图结构术语非常多，这里只介绍比较常见的术语

img

顶点:

  • 图中的一个节点
  • 比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人

边:

  • 顶点和顶点之间的连线
  • 比如地铁站中两个站点之间的直接连线，就是一个边
  • 上图: A-D 有一条边，D-F 有一条边，A-F 没有边

相邻顶点:

  • 由一条边连接在一起的顶点称为相邻顶点
  • 比如 A-D 是相邻的，D-F 是相邻的。A-F 是不相邻的

度:

  • 一个顶点的度是相邻顶点的数量
  • 比如 A 顶点和其他三个顶点相连，A 顶点的度是 3
  • 比如 C 顶点和其他五个顶点相连，C 顶点的度是 5

路径:

  • 路径是顶点的一个连续序列，比如上图中 ACE 就是一条路径
  • 简单路径: 简单路径要求不包含重复的顶点。比如 ACE 是一条简单路径
  • 回路: 第一个顶点和最后一个顶点相同的路径称为回路。 比如 ADCBA

无向图:

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

有向图:

  • 有向图表示的图中的边是有方向的

无权图:

  • 我们上面的图就是一张无权图(边没有携带权重)
  • 我们上面的图中的边是没有任何意义的
  • 不能说 A-D 的边，比 A-E 的边更远或者用的时间更长

带权图:

  • 带权图表示边有一定的权重
  • 这里的权重可以是任意你希望表示的数据
  • 比如距离或者花费的时间或者票价

图的表示 ​

怎么在程序中表示图呢?

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

顶点的表示相对简单，可以使用一个数组存储起来

那么边怎么表示呢？

  • 因为边是两个顶点之间的关系，所以表示起来会稍微麻烦一些

图结构的常见的两个表达方式：

  • 邻接矩阵
  • 邻接表

邻接矩阵 ​

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

  • 邻接矩阵让每个节点和一个整数项关联，该整数作为数组的下标值
  • 我们用一个二维数组来表示顶点之间的连接
  • 二维数组 [0][2] -> A-C

image-20231207153758184

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

邻接矩阵的问题:

  • 邻接矩阵还有一个比较严重的问题，就是如果图是一个稀疏图
  • 那么矩阵中将存在大量的 0，这意味着我们浪费了计算机存储空间来表示根本不存在的边

邻接表 ​

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

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

image-20231207155329251

  • 比如我们要表示和 A 顶点有关联的顶点（边），A 和 B/C/E 有边
  • 那么我们可以通过 A 找到对应的数组/链表/字典，再取出其中的内容就可以了

邻接表的问题:

  • 邻接表计算"出度"是比较简单的（出度: 指向别人的数量，入度: 指向自己的数量）
  • 邻接表如果需要计算有向图的”入度”，那么是一件非常麻烦的事情
  • 它必须构造一个"逆邻接表"，才能有效的计算"入度"。但是开发中"入度"相对用的比较少

图的实现 ​

创建图类 ​

创建 Graph 的构造函数。定义了两个属性:

  • vertices：用于存储所有的顶点，使用一个数组来保存
  • adjoinList：用于存储所有的边，这里采用邻接表的形式
typescript
class Graph<T> {
  vertices: T[] = []
  adjoinList: Map<T, T[]> = new Map()
}

图的添加 ​

添加顶点

  • 我们将添加的顶点放入到数组中
  • 另外，我们给该顶点创建一个数组，该数组用于存储顶点连接的所有的边

添加边

  • 添加边需要传入两个顶点，因为边是两个顶点之间的边，边不可能单独存在
  • 根据顶点 v 取出对应的数组，将 w 加入到它的数组中
  • 根据顶点 w 取出对应的数组，将 v 加入到它的数组中
  • 因为我们这里实现的是无向图，所以边是可以双向的
typescript
class Graph<T> {
  /** 添加顶点 */
  addVertex(vertex: T) {
    // 将顶点添加数组中保存
    this.vertices.push(vertex)
    // 创建一个邻接表的数组
    this.adjoinList.set(vertex, [])
  }
  /** 添加边 */
  addEdge(v1: T, v2: T) {
    this.adjoinList.get(v1)?.push(v2)
    this.adjoinList.get(v2)?.push(v1)
  }
  /** 遍历边 */
  traverse() {
    this.vertices.forEach(vertex => {
      const edges = this.adjoinList.get(vertex)
      console.log(`${vertex} -> ${edges?.join(' ')}`)
    })
  }
}

图的遍历 ​

图的遍历思想

  • 图的遍历思想和树的遍历思想是一样的
  • 图的遍历意味着需要将图中每个顶点访问一遍，并且不能有重复的访问

有两种算法可以对图进行遍历

  • 广度优先搜索（Breadth-First Search，简称 BFS）

    BFS: 基于队列，入队列的顶点先被探索

  • 深度优先搜索（Depth-First Search，简称 DFS）

    DFS: 基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就

  • 两种遍历算法，都需要明确指定第一个被访问的顶点

记录顶点是否被访问过，我们可以使用 Set 来存储被访问过的节点

广度优先搜索 ​

广度优先搜索算法的思路：

  • 广度优先算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层
  • 换句话说，就是先宽后深的访问顶点

image-20231207175337802

typescript
class Graph<T> {
  bfs() {
    // 1.判断是否有顶点
    if (this.vertices.length === 0) return
    // 2.创建队列结构访问每一个顶点
    const queue: T[] = []
    queue.push(this.vertices[0])
    // 3.创建Set结构，记录每一个顶点是否访问过
    const visited = new Set<T>()
    visited.add(this.vertices[0])
    // 4.遍历队列中每一个顶点
    while (queue.length) {
      // 访问队列中第一个顶点
      const vertex = queue.shift()! 
      console.log(vertex)
      // 相邻的顶点
      const neighbors = this.adjoinList.get(vertex)
      if (!neighbors) continue
      for (const nei of neighbors) {
        if (!visited.has(nei)) {
          visited.add(nei)
          queue.push(nei)
        }
      }
    }
  }
}

深度优先搜索 ​

深度优先搜索的思路:

  • 深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径知道这条路径最后被访问了
  • 接着原路回退并探索下一条路径

image-20231207175148864

typescript
class Graph<T> {
	/** 深度优先搜索 */
  dfs() {
    // 1.判断是否有顶点
    if (this.vertices.length === 0) return
    // 2.创建栈结构
    const stack: T[] = []
    stack.push(this.vertices[0])
    // 3.创建Set结构
    const visited = new Set<T>()
    visited.add(this.vertices[0])
    // 4.从第一个顶点开始访问
    while (stack.length) {
      const vertex = stack.pop()!
      console.log(vertex)
      const neighbors = this.adjoinList.get(vertex)
      if (!neighbors) continue
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const nei = neighbors[i]
        if (!visited.has(nei)) {
          visited.add(nei)
          stack.push(nei)
        }
      }
    }
  }
}

图的建模 ​

对交通流量建模

  • 顶点可以表示街道的十字路口，边可以表示街道
  • 加权的边可以表示限速或者车道的数量或者街道的距离
  • 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道

对非机航线建模

  • 航空公司可以用图来为其飞行系统建模将每个机场看成顶点
  • 将经过两个顶点的每条航线看作一条边
  • 加权的边可以表示从一个机场到另一个机场的航班成本，或两个机场间的距离
  • 建模人员可以利用这个系统有效的判断从一个城市到另一个城市的最小航行成本

图结构完整代码 ​

typescript
class Graph<T> {
  // 顶点
  vertices: T[] = []
  // 边：邻接表
  adjoinList: Map<T, T[]> = new Map()
  /** 添加顶点 */
  addVertex(vertex: T) {
    // 将顶点添加数组中保存
    this.vertices.push(vertex)
    // 创建一个邻接表的数组
    this.adjoinList.set(vertex, [])
  }
  /** 添加边 */
  addEdge(v1: T, v2: T) {
    this.adjoinList.get(v1)?.push(v2)
    this.adjoinList.get(v2)?.push(v1)
  }
  /** 遍历边 */
  traverse() {
    console.log('Graph:')
    this.vertices.forEach(vertex => {
      const edges = this.adjoinList.get(vertex)
      console.log(`${vertex} -> ${edges?.join(' ')}`)
    })
  }
  /** 广度优先搜索 */
  bfs() {
    // 1.判断是否有顶点
    if (this.vertices.length === 0) return
    // 2.创建队列结构访问每一个顶点
    const queue: T[] = []
    queue.push(this.vertices[0])
    // 3.创建Set结构，记录每一个顶点是否访问过
    const visited = new Set<T>()
    visited.add(this.vertices[0])
    // 4.遍历队列中每一个顶点
    while (queue.length) {
      // 访问队列中第一个顶点
      const vertex = queue.shift()!
      console.log(vertex)
      // 相邻的顶点
      const neighbors = this.adjoinList.get(vertex)
      if (!neighbors) continue
      for (const nei of neighbors) {
        if (!visited.has(nei)) {
          visited.add(nei)
          queue.push(nei)
        }
      }
    }
  }
  /** 深度优先搜索 */
  dfs() {
    // 1.判断是否有顶点
    if (this.vertices.length === 0) return
    // 2.创建栈结构
    const stack: T[] = []
    stack.push(this.vertices[0])
    // 3.创建Set结构
    const visited = new Set<T>()
    visited.add(this.vertices[0])
    // 4.从第一个顶点开始访问
    while (stack.length) {
      const vertex = stack.pop()!
      console.log(vertex)
      const neighbors = this.adjoinList.get(vertex)
      if (!neighbors) continue
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const nei = neighbors[i]
        if (!visited.has(nei)) {
          visited.add(nei)
          stack.push(nei)
        }
      }
    }
  }
}

常备不懈，才能有备无患