认识图结构

图结构是一种常见的数据结构。数学上有一个重要的分支叫做图论，其起源与“欧拉七桥”问题有关，有兴趣的同学可以自行了解。图论主要用于研究顶点和边组成的图形的数学理论和方法，应用于生活之中，就是研究事物（顶点）与事物之间的关系（边），比如地铁线路图。

图的表示方式

图结构通常有邻接矩阵和邻接表这 2 种表示方式，本篇文章将以代码的形式实现后者。

邻接表

比如，现在有一组顶点和边的关系如下图所示：

用邻接表来表示上示图结构如下：

上表的每一行，之后都将是一个 Map 对象，第 1 列，也就是各个顶点，作为 key；第 2 列，也就是该顶点的相邻顶点（由一条边连接在一起的顶点）装入一个数组作为 value。

邻接表的优缺点

邻接表的优点在于计算出度（指向的其它顶点的数量）非常方便，顺便一提，某个顶点的度，等于其相邻顶点的数量； 缺点在于计算入度（本身被别的顶点指向的次数）就比较复杂了。

代码实现

整体框架

我们定义一个 Graph 类来实现图结构。图结构通常的特点也就是 Graph 应该包含的属性：

1. 有一组顶点，我们可以用数组 vertex 来装载所有的顶点；
2. 还有一组边，我们用 Map 对象 edge 来表示。

class Graph {
  constructor() {
    this.vertex = [] // 顶点
    this.edge = new Map() // 边
  }
  // 下面添加方法
}

在图结构中，边是顶点和顶点之间的连线，它可以是有向的，比如顶点 A 和 B 之间有一条边，由 A 指向 B，那么从A 可以通向 B，但是从 B 不能通向 A，我们就说这是一个有向图；也可以是无向的，也就是 A 和 B 之间的边并没有方向，A 可以通向 B，B 也能通向 A，那么我们就说这是一个无向图。上面图 1 所示，即为无向图，也是我们接下去要实现的图结构。

方法

添加顶点 addVertex()

添加顶点时要做 2 件事：

1. 将顶点放入保存顶点（v）的数组 vertex；
2. 在 edge 对象，也就是一个 Map 对象添加一个指定该顶点为键（key），值（value）为空数组的新键值对。

// 添加顶点
addVertex(v) {
  this.vertex.push(v)
  this.edge.set(v, [])
}

添加边 addEdge()

addEdge() 方法传入要添加的边的两端的顶点 v1 与 v2 作为参数，因为是无向图，所以我们要通过 Map.prototype.get() 方法获取这两个顶点为键所对应的值，也就是存储相邻顶点的数组，然后分别进行添加。

// 添加边
addEdge(v1, v2) {
  this.edge.get(v1).push(v2)
  this.edge.get(v2).push(v1)
}

P.S. 边除了之前说的可以有方向外，还可以有权重，比如表示地铁线路的图结构里，边的权重就可以表示站点与站点之间的票价或是所需时间，那么我们就说这是一个带权图。而像图 1 这样的，边不带任何意义的，即为无权图。

toString()

toString() {
  let tempString = ''
  for (let i = 0; i < this.vertex.length; i++) {
    tempString += this.vertex[i] + '===>'
    const tempArr = this.edge.get(this.vertex[i])
    for (let j = 0; j < tempArr.length; j++) {
      tempString += tempArr[j] + '\0'
    }
    tempString += '\n'
  }
  return tempString
}

toString 方法就是循环遍历每个顶点，在每次循环中，再循环遍历存储在 edge 里 key 为该顶点的 value，也就是各个顶点的相邻顶点组成的数组，然后进行字符串拼接。 下面按照图 1，进行顶点和边的添加，利用 toString() 方法对代码是否正确进行测试。

const graph = new Graph()
const vertexList = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
vertexList.forEach((v) => graph.addVertex(v))
graph.addEdge('A', 'B')
graph.addEdge('A', 'D')
graph.addEdge('B', 'C')
graph.addEdge('C', 'D')
graph.addEdge('C', 'E')
graph.addEdge('C', 'F')
graph.addEdge('E', 'F')
graph.addEdge('F', 'G')
console.log(graph.toString())

打印结果如下： 与表 1 一致，说明目前为止代码的运行是符合预期的。

图的遍历

遍历图结构需要将图里的每一个顶点都访问一遍，并且不能重复。下面介绍 2 种遍历算法，它们都需要明确指定第一个被访问的顶点，即源顶点 s。另外，遍历过程会为顶点置色，以反映各个顶点的状态：

• 白色代表顶点未被访问；
• 黑色代表该顶点以及其所有相邻顶点都被访问过了；
• 灰色则代表该顶点被访问过，但其相邻顶点中还有未被访问过的白色顶点存在。

所以在最开始我们需要定义个初始化颜色的方法 initColor()，代码如下：

// 初始化颜色
initColor() {
  const colorMsg = {}
  this.vertex.forEach((v) => (colorMsg[v] = 'white'))
  return colorMsg
}

宽度优先搜索（Breadth First Search, BFS）

又称广度优先搜索。从顶点 s 开始遍历，将顶点放入一个 队列 Q 中，并置灰，Q 中的顶点先被探索，即访问其所有相邻顶点。如果队列 Q 非空，则执行下列步骤：

1. 从队列取出一个顶点 v；
2. 访问其所有相邻顶点，将它们中未被访问过的白色顶点加入到 Q 中并置灰；
3. 将 v 置黑。

代码如下：

// 宽度优先搜索
bfs(v) {
  const colorMsg = this.initColor() // 将所有顶点的颜色初始化为白色
  const queue = new Queue()
  queue.push(v)
  while (!queue.isEmpty()) {
    const outVertex = queue.shift()
    const adjacentVertex = this.edge.get(outVertex)
    adjacentVertex.forEach((item) => {
      if (colorMsg[item] === 'white') {
        queue.push(item)
        colorMsg[item] = 'grey'
      }
    })
    colorMsg[outVertex] = 'black'
    console.log(outVertex)
  }
}

BFS 的特点就是先宽后深，一层层地访问各个顶点。遍历图 1 这样的结构顺序应该如下图所示：

执行 graph.bfs('A') 进行测试，打印结果如下：

顺序符合图 2 的预期。

深度优先搜索（Depth First Search, DFS）

DFS 的实现可以基于栈或是使用递归，对每一个可能的分支路径深入到不能再深入为止，并且每个顶点只访问一次。以图 1 为例，步骤如下：

1. 最开始所有顶点依然为白色；
2. 从顶点 A 开始访问，之后访问 B，再访问 C，访问过的顶点置灰；
3. C 的相邻顶点有 D、E 和 F，因为添加顶点时先添加的是 D，所以先访问 D，D 之后没有顶点了，即 D 的所有相邻顶点都访问过了，将 D 置黑，再沿着原来的访问路径返回到顶点 C，判断 C 是否有未被访问的相邻顶点，发现有 E 和 F，则从 E 开始，再次进行深度优先遍历。图示如下：

P.S. 所谓路径，就是由像图 1 中顶点 A、B、C、F 和 G组成的连续序列。路径还可分为简单路径：不包含重复顶点； 和回路：第一个和最后一个顶点是同一个顶点的路径。

下面是使用递归实现的 DFS 方法，递归其实就是函数栈的调用：

// 深度优先搜索
dfs(v) {
  const colorMsg = this.initColor()
  this.dfsVisit(v, colorMsg)
}
// 递归方法
dfsVisit(v, colorMsg) {
  colorMsg[v] = 'grey'
  console.log(v)
  const adjacentVertex = this.edge.get(v)
  adjacentVertex.forEach((item) => {
    if (colorMsg[item] === 'white') {
      this.dfsVisit(item, colorMsg)
    }
  })
  colorMsg[v] = 'black'
}