1. 认识图结构

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

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. 邻接矩阵和邻接表

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

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

3.1 邻接矩阵

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

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

图片解析：

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

邻接矩阵的问题：

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

3.2 邻接表

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

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

邻接表的问题

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

出度：指向别人的数量

入度：指向自己的数量

4. 图结构的封装

4.1 图的基础框架 v1 版

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

  constructor() {}
}

解析：

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

4.2 添加基础方法 V2 版本

addVertex：添加顶点的方法

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

addEdge：添加边的方法

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

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

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

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

测试:

ts
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）

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

ts
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）

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

ts
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);
      }
    }
  }
}

目录