图（Graph）结构

核心特性

由顶点（Vertex）和边（Edge）组成，支持有向 / 无向、加权 / 无权

核心操作：添加顶点、添加边、遍历（深度优先 DFS / 广度优先 BFS）

实现方式：邻接矩阵（二维数组）、邻接表（对象 / 数组，更节省空间）

代码实现（邻接表）

class Graph {
  constructor() {
    this.vertices = new Set(); // 存储所有顶点
    this.adjList = new Map(); // 邻接表：key=顶点，value=相邻顶点数组
  }

  // 添加顶点
  addVertex(vertex) {
    if (!this.vertices.has(vertex)) {
      this.vertices.add(vertex);
      this.adjList.set(vertex, []);
    }
  }

  // 添加边（无向图：双向添加）
  addEdge(v1, v2) {
    // 确保顶点存在
    this.addVertex(v1);
    this.addVertex(v2);
    // 无向图：v1的邻接表添加v2，v2的邻接表添加v1
    this.adjList.get(v1).push(v2);
    this.adjList.get(v2).push(v1);
  }

  // 深度优先遍历（DFS，递归实现）
  dfs(startVertex, visited = new Set(), result = []) {
    if (!this.vertices.has(startVertex)) return result;
    if (visited.has(startVertex)) return result;

    visited.add(startVertex);
    result.push(startVertex);

    // 遍历相邻顶点
    const neighbors = this.adjList.get(startVertex);
    for (const neighbor of neighbors) {
      this.dfs(neighbor, visited, result);
    }
    return result;
  }

  // 广度优先遍历（BFS，队列实现）
  bfs(startVertex) {
    const result = [];
    const visited = new Set();
    const queue = [startVertex];

    if (!this.vertices.has(startVertex)) return result;
    visited.add(startVertex);

    while (queue.length) {
      const current = queue.shift();
      result.push(current);

      // 遍历相邻顶点
      const neighbors = this.adjList.get(current);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return result;
  }
}

适用场景

路由跳转关系：如单页应用的路由跳转图（A 页面→B 页面→C 页面，有向图），用于分析路由依赖

依赖关系分析：Webpack 模块依赖图（每个模块是顶点，依赖关系是边），用于按需加载

社交网络：用户关系图（用户是顶点，好友关系是边），用于查找共同好友、推荐好友

注意

图的遍历需标记已访问顶点（避免循环遍历，如 A→B→A）

邻接表比邻接矩阵更适合稀疏图（顶点多、边少），节省空间