Z
Toggle Nav

无向图

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

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

临接矩阵 有两个主要限制:

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

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

临接表数组

临接表数组如上图,实现上非常简单:

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

DFS

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

无向图的 DFS 很简单,核心思路为:

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

简单的代码表示为:

export class DFSSearch {
  // 存储访问标记
  private visitedMap = new Map<number, boolean>();

  /**
   * 创建搜索
   * @param graph 图
   * @param start 起点顶点
   */
  constructor(protected graph: IGraph, protected start: number) {
    this.dfs(start);
  }

  /**
   * 从一个顶点开始dfs
   * @param v 顶点
   */
  private dfs(v: number) {
    // 标记当前顶点访问过
    this.visitedMap.set(v, true);

    // 遍历顶点 v 的所有边,ev 是这条边的另一个顶点
    for (const ev of this.graph.getAdj(v)) {
      // 如果边的另一个顶点没访问过,则访问他
      if (!this.visited(ev)) {
        this.dfs(ev);
      }
    }
  }

  public visited(v: number) {
    return this.visitedMap.has(v);
  }
}