原文来自我的个人博客

1. 认识图结构

1. 图是网络结构的抽象模型，是一组由边连接的节点。
2. 图可以表示任何二元关系。
3. js 中没有图，但是可以用 Object 构建图
4. 图的表示法有：邻接矩阵、邻接表、关联矩阵......

2. 图结构常见术语

1. 顶点

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

2. 边

• 表示顶点到顶点的连线
• 比如地铁站中两个站点之间的直接连线，就是一个边

3. 相邻顶点

• 表示由一条边连接在一起的顶点

4. 度

• 一个顶点的度表示相邻顶点的数量
• 比如上图中 0 顶点和其他两个顶点相连，所以 0 顶点的度是 2

5. 路径

• 路径是顶点之间的一个连续序列，比如上图中0 1 5 9就是一条路径
• 简单路径： 要求不包含重复的顶点，比如 0 1 5 9
• 回路： 第一个顶点和最后一个顶点相同的路径，比如 0 1 5 6 3 0

5. 无向图

• 表示所有边都没有方向
• 比如上图中 0 - 1 之间有边且没有方向，说明这条边可以保证 0 -> 1，也可以保证 1 -> 0

6. 有向图

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

7. 无权图

• 表示边没有携带权重

8. 带权图

• 带权图表示边有一定的权重
• 这里的权重可以是任意你希望表示的数据

3. 邻接矩阵和邻接表

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

1. 顶点的表示：顶点可以使用数组来存储
2. 边的表示：边的表示会稍微麻烦一些，下面我们具体讨论一下边常见的表示方式

3.1 邻接矩阵

邻接矩阵是一种常见的表示图的方式

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

图片解析：

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

邻接矩阵的问题：

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

3.2 邻接表

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

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

邻接表的问题

邻接表计算 “出度” 是比较简单的，但是如果计算有向图的 “入度”，就是一件非常麻烦的事情，它必须构造一个 “逆邻接表”，才能有效的计算 “入度”

出度：指向别人的数量

入度：指向自己的数量

4. 图结构的封装

4.1 图的基础框架 v1 版

class Graph<T> {
  verteces: T[] = [];
  adjList: Map<T, T[]> = new Map();

  constructor() {}
}

解析：

1. verteces：用于存储所有的顶点，
2. adjList：adj 是 adjoin 的缩写，邻接的意思。adjList 用于存储所有的边，我们这里采用邻接表的形式。

4.2 添加基础方法 V2 版本

1. addVertex：添加顶点的方法

/* 添加顶点的方法 */
addVertex(vertex: T) {
  // 将顶点添加数组中保存
  this.verteces.push(vertex);
  // 创建一个邻接表中的数组
  this.adjList.set(vertex, []);
}

1. addEdge：添加边的方法

/* 添加边的方法 */
addEdge(v1: T, v2: T) {
  this.adjList.get(v1)?.push(v2);
  this.adjList.get(v2)?.push(v1);
}

1. traverse：一个打印的方法，方便我们看结构

traverse() {
  this.verteces.forEach((vertex) => {
    const edges = this.adjList.get(vertex);

    console.log(`${vertex} -> ${edges?.join(" ")}`);
  });
}

测试:

const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B");
graph.addEdge("A", "D");
graph.addEdge("B", "B");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("C", "D");
graph.addEdge("F", "A");

graph.traverse();

打印结果：

A -> B D F
B -> A B B
C -> E D
D -> A E C
E -> C D
F -> A

4.3 深度优先遍历 v3 版

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

思想：基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

dfs() {
  // 1. 判断是否有顶点
  if (this.verteces.length === 0) return;

  // 2. 创建队列结构访问每一个顶点
  const stack: T[] = [];
  stack.push(this.verteces[0]);

  // 3. 创建 Set 结构，记录某一个顶点是否被访问过
  const visited = new Set<T>();
  visited.add(this.verteces[0]);

  // 4. 从第一个顶点开始访问
  while (stack.length) {
    const vertex = stack.pop()!;
    console.log(vertex);

    const neighbors = this.adjList.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);
      }
    }
  }
}

4.4 广度优先遍历 v4 版

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

思想：基于队列，入队列的顶点先被探索

bsf() {
  // 1. 判断是否有顶点
  if (this.verteces.length === 0) return;

  // 2. 创建队列结构访问每一个顶点
  const queue: T[] = [];
  queue.push(this.verteces[0]);

  // 3. 创建 Set 结构，记录某一个顶点是否被访问过
  const visited = new Set<T>();
  visited.add(this.verteces[0]);

  // 4. 遍历队列中每一个顶点
  while (queue.length) {
    // 访问队列中第一个顶点
    const vertex = queue.shift()!;
    console.log(vertex);

    // 相邻的顶点
    const neighbors = this.adjList.get(vertex);
    if (!neighbors) continue;
    for (const nei of neighbors) {
      if (!visited.has(nei)) {
        visited.add(nei);
        queue.push(nei);
      }
    }
  }
}