高级数据结构

图的表示与遍历

图 = 树 + 环

前面所有树的算法都建立在一个前提上：从父节点走到子节点，永远回不来。 图没有这个保证，于是每一次遍历都必须记 visited， 否则就是无限循环（网格 DFS 那篇实测过：RangeError 栈溢出， 不是程序卡住）。

除此之外，图上的 DFS 和 BFS 与树上的几乎一模一样。

两种表示法

// 邻接表：每个节点一个邻居列表
const adjList = [[1, 2], [2], [0], []];        // 0→1, 0→2, 1→2, 2→0

// 邻接矩阵：m[i][j] 表示 i 到 j 有没有边
const adjMatrix = [
  [0, 1, 1, 0],
  [0, 0, 1, 0],
  [1, 0, 0, 0],
  [0, 0, 0, 0],
];
邻接表 邻接矩阵
空间 O(V + E) O(V²)
遍历某点的所有邻居 O(度数) O(V)
判断 i→j 是否有边 O(度数) O(1)
适合 稀疏图（大多数题） 稠密图、频繁查边

⭐ 默认用邻接表。V=10⁵ 的图用矩阵要 10¹⁰ 个格子，直接爆内存。

📌 判据比比例有用（「算法题里 95% 用邻接表」这类话没法验，别当依据）：

只有同时满足「V 小到 V² 装得下」和「反复问 i、j 之间通不通」时才选矩阵。

前一条通常意味着 V ≲ 数千（V=5000 时矩阵已是 2500 万格）。 两条缺一条就用邻接表 —— 稠密图本身不是理由，因为邻接表在稠密图上 空间只是 O(E)≈O(V²) 打平，而遍历邻居仍然更快。

🚨 环检测：两个集合，撤销规则相反

回溯与 DFS 那篇详细讲过这一条， 这里给完整代码：

function hasCycle(n, adj) {
  const visited = new Set();   // 这辈子访问过 —— 不撤销
  const onPath = new Set();    // 在当前这条路径上 —— 必须撤销
  let found = false;

  function dfs(u) {
    if (onPath.has(u)) { found = true; return; }   // 撞上自己走过的路
    if (visited.has(u)) return;                    // 之前查过，不必再查

    visited.add(u);
    onPath.add(u);
    for (const v of adj[u]) dfs(v);
    onPath.delete(u);                              // 只删这一个
  }

  for (let i = 0; i < n; i++) dfs(i);
  return found;
}

⚠️ 两种错法的症状完全不同：onPath 不撤销会把菱形 DAG 误判成有环； visited 也撤销则结果正确但退化成枚举所有路径（那篇实测过 43 次 vs 65519 次调用）。

📌 判据一句话：这个标记描述的是「历史」还是「当前路径」？历史不撤，路径必撤。

拓扑排序：BFS 版更好写

拓扑排序 = 把有向无环图排成一列，使每条边都从前指向后。

function topoSort(n, adj) {
  // ① 统计入度
  const indeg = new Array(n).fill(0);
  for (let u = 0; u < n; u++) for (const v of adj[u]) indeg[v]++;

  // ② 入度为 0 的先入队
  const q = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);

  // ③ 每弹出一个，就把它的邻居入度减一，减到 0 就入队
  const order = [];
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }

  // ⭐ 排不完 = 有环
  return order.length === n ? order : null;
}

⭐ 最后那一行是白送的环检测。 有环的话环上的节点入度永远减不到 0， 排出来的序列就短了。所以「判断课程表能否修完」这类题， 直接跑拓扑排序看长度就行，不用另写 hasCycle。

⚠️ 拓扑序通常不唯一（多个入度为 0 的点谁先出都行）。 题目如果要求「字典序最小的拓扑序」，把队列换成小顶堆即可。

🚨 --indeg[v] === 0 里是前置递减。写成 indeg[v]-- === 0 比较的是 减之前的值 —— 而任何有入边的节点，减之前都不可能是 0 （入度本来就是 0 的点早在初始队列里了）。于是没有任何节点会被追加入队， order 里只剩最初那批。

⭐ 好消息是这个错几乎藏不住：实测在链、菱形、单层依赖的图上全部返回 null， 只有完全没有边的图才碰巧对（那时初始队列已经装下了所有节点）。

链 0→1→2        正确 [0,1,2]      错版 null
菱形             正确 [0,1,2,3]    错版 null
单层 0→2, 1→2    正确 [0,1,2]      错版 null
无边图            正确 [0,1,2]      错版 [0,1,2]   ← 唯一碰巧对的

⚠️ 对比一下这个板块里其他那些「结果对、只是慢」的坑 —— 这一个反而是最容易发现的，因为它一有边就炸。

二分图判定：染色

二分图 = 能把所有点分成两组，使每条边的两端在不同组。

function isBipartite(n, adj) {
  const color = new Array(n).fill(0);   // 0 未染，1 和 -1 是两种颜色

  for (let s = 0; s < n; s++) {
    if (color[s] !== 0) continue;
    color[s] = 1;
    const q = [s];
    let head = 0;
    while (head < q.length) {
      const u = q[head++];
      for (const v of adj[u]) {
        if (color[v] === 0) { color[v] = -color[u]; q.push(v); }
        else if (color[v] === color[u]) return false;   // 相邻同色 → 不是二分图
      }
    }
  }
  return true;
}

🚨 外层那个 for (let s = 0; ...) 不能省。图可能不连通 —— 只从 0 号点出发的话，其他连通分量根本没被检查。 ⚠️ 这个错在连通图上完全不出现，而大部分测试用例都是连通的。

📌 一条有用的等价说法：二分图 ⇔ 图中没有奇数长度的环。 面试里能顺口说出这句，比只会写染色代码显得更懂。

下一步

图的连通性问题（「这两个点连不连通」「有几个连通分量」） 用 DFS/BFS 能做，但每次查询都要重新遍历。 并查集是这类问题的专用结构，接近 O(1)。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。