深度优先搜索与图的表示 - 算法与数据结构教程

讲解

图是节点加边的结构，是最一般化的数据结构——树是特殊的图（无环连通），链表是特殊的树（每节点一个孩子）。图的两种主流表示各有适用场景。邻接矩阵：n×n 的二维数组，matrix[i][j] 表示 i 到 j 有无边，查询 O(1) 但空间 O(n²)，适合稠密小图。邻接表：每个节点挂一个邻居列表，空间 O(n+e)，遍历邻居快，是绝大多数算法题的选择。拿到题先看规模：节点上万一律邻接表。

图的 DFS 与树的 DFS 的唯一区别是：图可能有环，必须用 visited 标记防止绕圈。还有一个更精细的三态标记：0 未访问、1 访问中（在当前递归栈上）、2 已完成。状态 1 被再次碰到就说明发现了环——这是拓扑排序判环的核心机制。

拓扑排序解决「有依赖关系的任务该按什么顺序执行」：课程表（先修课关系）、编译顺序、任务调度。它只存在于有向无环图（DAG）上。DFS 版本的洞察很漂亮：一个节点在它的所有后继完成之后才被「结算」，所以把 DFS 的完成时刻倒序排列，就是拓扑序。若过程中发现环，则无拓扑序（先修课互相依赖，谁都修不了）。另一个主流解法是 Kahn 算法（BFS + 入度表），思想是「每轮摘掉入度为 0 的节点」，两种都要会。

无向图的连通分量计数（省份数量）则是 DFS 的暖场应用：每发现一个未访问节点就计数加一并 DFS 淹没整个分量——和岛屿数量完全同构，只是网格换成了邻接矩阵。

示例

邻接表建图 + 课程表（三色 DFS 判环并产出拓扑序）+ 省份数量（DFS 数连通分量）：

import assert from 'node:assert/strict';

// 边列表 -> 邻接表
function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [from, to] of edges) {
    graph[from].push(to);
  }
  return graph;
}

// 课程表 II：返回一个可行修课顺序，有环则返回 []
function findOrder(numCourses, prerequisites) {
  // 边 [a, b] 表示先修 b 再修 a，即 b -> a
  const graph = buildGraph(numCourses, prerequisites.map(([a, b]) => [b, a]));
  const state = new Array(numCourses).fill(0); // 0 未访问 1 访问中 2 已完成
  const order = [];
  let hasCycle = false;
  function dfs(node) {
    if (state[node] === 1) {
      hasCycle = true; // 碰到递归栈上的节点：有环
      return;
    }
    if (state[node] === 2) return;
    state[node] = 1;
    for (const next of graph[node]) dfs(next);
    state[node] = 2;
    order.push(node); // 完成时刻入列，最后整体倒序
  }
  for (let i = 0; i < numCourses; i++) dfs(i);
  return hasCycle ? [] : order.reverse();
}

// 省份数量：无向图连通分量计数（邻接矩阵输入）
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;
  function dfs(city) {
    visited[city] = true;
    for (let other = 0; other < n; other++) {
      if (isConnected[city][other] === 1 && !visited[other]) dfs(other);
    }
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      provinces++;
      dfs(i);
    }
  }
  return provinces;
}

assert.deepStrictEqual(findOrder(2, [[1, 0]]), [0, 1]);
assert.deepStrictEqual(findOrder(2, [[1, 0], [0, 1]]), []); // 互相依赖，无解

const order4 = findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]);
assert.strictEqual(order4.length, 4);
// 拓扑序合法当且仅当：每条依赖的前驱都排在后继之前
assert.ok(order4.indexOf(0) < order4.indexOf(1));
assert.ok(order4.indexOf(0) < order4.indexOf(2));
assert.ok(order4.indexOf(1) < order4.indexOf(3));
assert.ok(order4.indexOf(2) < order4.indexOf(3));

assert.strictEqual(
  findCircleNum([
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
  ]),
  2,
);
assert.strictEqual(
  findCircleNum([
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1],
  ]),
  3,
);

console.log('图的 DFS 示例全部通过');

验证拓扑序的方式本身就是个知识点：拓扑序不唯一，断言不该写死某一个顺序，而应检查「每条依赖边的前驱都在后继之前」——写测试时断言性质而非具体值，这个习惯在工程中也通用。

常见坑

图 DFS 忘加 visited：无环树不需要，但图有环，不标记直接死循环爆栈。
三态标记用成两态：判环必须区分「访问中」和「已完成」——访问到已完成节点是跨边而非环。
边的方向建反：课程表 [a, b] 的语义是「先 b 后 a」，建图是 b -> a；方向反了答案也反。
拓扑序断言写死：合法拓扑序可能很多，逐条依赖验证才是正确姿势。
邻接矩阵遍历漏掉对称性：无向图矩阵对称，遍历整行即可，别再反向走一次；有向图则要注意行和列的含义。

小结

图用邻接表（稀疏）或邻接矩阵（稠密小图）表示；图 DFS 必须带 visited，判环用三态标记；拓扑排序 = DFS 完成时刻倒序（或 Kahn 摘入度 0 节点）。下一章看专为「连通性」而生的结构：并查集。