有向图环检测

功能说明

该示例检测有向图中是否存在环，并返回一条可直接用于报错的闭合路径，例如 a -> b -> c -> a；若图是有向无环图则返回 null。常用于依赖图校验、构建流水线排序前检查、状态机配置验证以及包管理器安装前的循环依赖排查。邻接表用 ReadonlyMap 表示，键是节点，值是该节点的出边列表。

关键代码

节点有三种颜色：白色表示未访问，灰色表示正在当前递归栈中，黑色表示已完成。进入节点时标灰并入栈；遍历邻居时若遇到灰色节点，说明存在回边，从栈中找到该邻居的位置并切出子路径，再追加邻居形成闭合环。若邻居为白色则递归访问。节点所有出边处理完后出栈并标黑。外层循环保证非连通图的所有分量都会被检查。

使用注意

递归实现受调用栈深度限制，超长依赖链可能栈溢出，生产环境可改写为显式栈的迭代版本。返回的路径可能不是最短环，只是 DFS 首次发现的那条。只检查从图键出发的节点，但邻居中未登记的节点也会被访问并标黑。自环会返回首尾相同的两元素路径。图在检测过程中不会被修改。

验证方式

构造三节点闭环，断言返回路径首尾相同且包含全部节点；构造含自环的图，验证返回两个相同节点；测试完全无环的 DAG 返回 null；构造多个不连通分量且环在后面的图，确认仍能发现；用只作为邻居出现、未作为键登记的节点验证不会崩溃；检查原 Map 与邻接数组未被修改。

代码示例

const WHITE = 0;
const GRAY = 1;
const BLACK = 2;

export function findCycle(
  graph: ReadonlyMap<string, readonly string[]>,
): string[] | null {
  const state = new Map<string, number>();
  const stack: string[] = [];

  const visit = (node: string): string[] | null => {
    state.set(node, GRAY);
    stack.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      const color = state.get(neighbor) ?? WHITE;
      if (color === GRAY) {
        const start = stack.indexOf(neighbor);
        return [...stack.slice(start), neighbor];
      }
      if (color === WHITE) {
        const cycle = visit(neighbor);
        if (cycle) return cycle;
      }
    }
    stack.pop();
    state.set(node, BLACK);
    return null;
  };

  for (const node of graph.keys()) {
    if ((state.get(node) ?? WHITE) === WHITE) {
      const cycle = visit(node);
      if (cycle) return cycle;
    }
  }
  return null;
}