中文
devexamples

Topological Sort With Cycle Detection (JavaScript)

Order a dependency graph so every node appears after its prerequisites, reporting a cycle when no valid order exists.

JavascriptData Integrity

Code

snippet
export function topologicalSort(graph) {
  const visited = new Set();
  const inStack = new Set();
  const order = [];
  const visit = (node) => {
    if (inStack.has(node)) throw new Error("cycle detected at " + node);
    if (visited.has(node)) return;
    inStack.add(node);
    for (const dep of graph.get(node) ?? []) visit(dep);
    inStack.delete(node);
    visited.add(node);
    order.push(node);
  };
  for (const node of graph.keys()) visit(node);
  return order;
}

Related Examples