数据结构图详解与基础概念

什么是图

图（Graph）是由顶点（Vertex）和连接顶点的边（Edge）组成的网络结构。跟链表、树相比，图的约束最少：链表每个节点只有一个后继，树每个节点只有一个父节点，而图里任意两个顶点之间都可以有边，允许成环，也允许一个顶点连很多个顶点。

树其实就是一种特殊的图——无环连通图。所以掌握了图的遍历，树的遍历只是它的一个特例。

基础概念

理解下面这几个术语，看图相关的题目会顺很多。

顶点：图里的基本单元，也叫节点
边：两个顶点之间的连接
度：一个顶点连接的边的数量。有向图里还要分入度（指向它的边数）和出度（从它出发的边数）
有向图 / 无向图：边有方向的是有向图（比如网页之间的超链接），没方向的是无向图（比如微信好友关系）
权：边上附加的数值，比如两个城市之间的距离。带权的叫加权图
路径：从一个顶点到另一个顶点经过的顶点序列
环：起点和终点是同一个顶点的路径
连通：两个顶点之间存在路径就叫连通。无向图里任意两顶点都连通叫连通图

JS 中怎么表示图

JS 里没有内置的图类型，通常用两种方式表示。

邻接矩阵

用一个二维数组，matrix[i][j] 表示顶点 i 到顶点 j 有没有边（加权图里存权值）：

// 顶点 0,1,2,3，无向图
const matrix = [
  [0, 1, 1, 0], // 0 连 1、2
  [1, 0, 0, 1], // 1 连 0、3
  [1, 0, 0, 1], // 2 连 0、3
  [0, 1, 1, 0], // 3 连 1、2
];

无向图的邻接矩阵一定是沿对角线对称的。查「i 和 j 之间有没有边」是 O(1)，但空间是 O(V²)，顶点多而边少（稀疏图）时非常浪费。

邻接表

用对象或 Map 存每个顶点的邻居列表，这是实际写题时更常用的形式：

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2],
};

空间是 O(V + E)，遍历某个顶点的所有邻居很直接。代价是判断「i 和 j 之间有没有边」要扫一遍邻居列表。

深度优先遍历

深度优先（DFS）的思路是沿着一条路一直走到底，走不通再回退换一条。用递归实现最自然，关键点是必须有一个 visited 集合记录访问过的顶点，否则图里有环时会无限递归：

const visited = new Set();

const dfs = n => {
  console.log(n);
  visited.add(n);
  graph[n].forEach(c => {
    if (!visited.has(c)) {
      dfs(c);
    }
  });
};

dfs(0); // 0 1 3 2

树的遍历不需要 visited，因为树无环；图必须要。这是从树迁移到图时最容易漏掉的一步。

广度优先遍历

广度优先（BFS）是一层一层往外扩：先访问所有距离为 1 的顶点，再访问距离为 2 的。实现上用队列，把当前顶点的未访问邻居全部入队：

const visited = new Set([0]);
const q = [0];

while (q.length) {
  const n = q.shift();
  console.log(n);
  graph[n].forEach(c => {
    if (!visited.has(c)) {
      q.push(c);
      visited.add(c);
    }
  });
}
// 0 1 2 3

这里有个细节：visited.add(c) 必须在入队时做，不能等出队时再加。如果等出队才标记，同一个顶点可能被多个邻居重复入队，队列里出现重复元素，轻则多做无用功，重则在稠密图里爆内存。

另外 q.shift() 是 O(n) 操作（要移动后面所有元素），数据量大时用一个下标指针代替出队更高效：

let head = 0;
while (head < q.length) {
  const n = q[head++];
  // ...
}

什么时候用哪个

BFS 天然能求无权图的最短路径，因为它是按距离分层扩展的，第一次到达某个顶点时走的一定是最短路。DFS 不保证这一点，但在求「是否存在路径」「找所有路径」「拓扑排序」「判环」这类问题上写起来更简洁。

加权图的最短路径 BFS 就不行了，要用 Dijkstra 之类的算法。

实际场景

社交关系：好友推荐就是在图上找距离为 2 的顶点
路径规划：地图导航是加权有向图的最短路径问题
依赖解析：npm 的依赖树本质是有向图，循环依赖就是图里出现了环
前端路由：页面跳转关系可以建模成有向图