Z

无向图

无向图是图数据结构中最简单的一种，它通常使用 临接表数组 实现：

另一种高效方式是使用 临接矩阵 实现：

但 临接矩阵 有两个主要限制：

  1. 空间消耗较多，需要创建 nxn 的矩阵，且创建后不易更改大小
  2. 无法表示 平行边

如果对于图的需求并不包含上述两个，那么 临接矩阵 不失为一种简单可行的办法。这里主要采用 临接表数组 来实现无向图。

临接表数组

临接表数组如上图，实现上非常简单：

1class UndirectedGraph {
2    // Map 的 key 存储一个 `顶点`, value 存储该顶点的所有 `相邻顶点`
3    private store = new Map<number, number[]>();
4}

DFS

搜索一张图最常规的方法是 DFS (Depth First Search)，DFS 也存在与树搜索中，树的 DFS 与图的 DFS 略有不同，但两者均为同一思想：尽可能深地搜索分支，直到该分支已到底才切换另一条分支。

无向图的 DFS 很简单，核心思路为：

  1. 任选图中的一个顶点，从该顶点( \(A\) )开始搜索
  2. 标记 \(A\) 为 已访问过
  3. 遍历该顶点( \(A\) )的的所有相邻顶点( \(B_i\) )，如果 \(B_i\) 未被 访问过，则从 \(B_i\) 重新开始搜索。

简单的代码表示为：

 1export class DFSSearch {
 2  // 存储访问标记
 3  private visitedMap = new Map<number, boolean>();
 4
 5  /**
 6   * 创建搜索
 7   * @param graph 图
 8   * @param start 起点顶点
 9   */
10  constructor(protected graph: IGraph, protected start: number) {
11    this.dfs(start);
12  }
13
14  /**
15   * 从一个顶点开始dfs
16   * @param v 顶点
17   */
18  private dfs(v: number) {
19    // 标记当前顶点访问过
20    this.visitedMap.set(v, true);
21
22    // 遍历顶点 v 的所有边，ev 是这条边的另一个顶点
23    for (const ev of this.graph.getAdj(v)) {
24      // 如果边的另一个顶点没访问过，则访问他
25      if (!this.visited(ev)) {
26        this.dfs(ev);
27      }
28    }
29  }
30
31  public visited(v: number) {
32    return this.visitedMap.has(v);
33  }
34}