中文
devexamples

Cycle Detection In Directed Graphs

Detect directed cycles with three-color depth-first search, returning a concrete closed path for diagnostics or null for a DAG.

TypescriptData Integrity

Code

snippet
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;
}

Related Examples