有向图中的检测循环

Question

最近不得不在代码逻辑中检测有向图中的递归。我的nodejs实现感觉很复杂，我现在想知道：

• 代码有问题吗？
• 我们可以简化它/使其更具可读性吗？

const checkCyclic = (graph) => {
  const nodes = new Set(Object.keys(graph));
  const searchCycle = (trace, node) => {
    const cycleStartIdx = trace.indexOf(node);
    if (cycleStartIdx !== -1) {
      throw new Error(`Cycle detected: ${trace
        .slice(cycleStartIdx).concat(node).join(' <- ')}`);
    }
    if (nodes.delete(node) === true) {
      const nextTrace = trace.concat(node);
      graph[node].forEach((nextNode) => searchCycle(nextTrace, nextNode));
    }
  };
  while (nodes.size !== 0) {
    searchCycle([], nodes.values().next().value);
  }
};

checkCyclic({
  p1: ['p3'],
  p2: ['p1'],
  p3: ['p2']
});
// => Recursion detected: p1 <- p3 <- p2 <- p1

checkCyclic({
  p0: ['p1'],
  p1: ['p3'],
  p2: ['p1'],
  p3: ['p2']
});
// => Recursion detected: p1 <- p3 <- p2 <- p1

checkCyclic({
  p0: ['p0']
});
// => Cycle detected: p0 <- p0

出于好奇，它在promise-pool-ext中使用，其中也包含测试。

非常感谢您的反馈！

---

Edit：反复尝试并执行了迭代实现（看起来更难看！）

module.exports = (G) => {
  const pending = new Set(Object.keys(G));
  while (pending.size !== 0) {
    const stack = [pending.values().next().value];
    const stackParentIdx = [0];
    pending.delete(stack[0]);

    while (stack.length !== 0) {
      const c = stack.length - 1;
      const n = stack[c];
      const parents = G[n];
      const parentsIdx = stackParentIdx[c];
      if (parentsIdx < parents.length) {
        stackParentIdx[c] += 1;
        const parent = parents[parentsIdx];
        if (stack.includes(parent)) {
          throw new Error(`Cycle detected: ${stack
            .slice(stack.indexOf(parent)).concat(parent).join(' <- ')}`);
        }
        if (pending.delete(parent)) {
          stack.push(parent);
          stackParentIdx.push(0);
        }
      } else {
        stack.pop();
        stackParentIdx.pop();
      }
    }
  }
};

我通常更喜欢迭代而不是递归，但是在这种情况下，可能不值得在可读性上进行权衡。知道如何改进此实现吗？

Answer 1

我们可能会缩短一点：

function getCycle (G, n, path) {
  if (path.includes(n)) {
    throw `cycle ${path.slice(path.indexOf(n)).concat(n).join('<-')}`
  }
  path.push(n)
  return G[n].forEach(next => getCycle(G, next, path.slice(0)))
}
function validate (G) {
  Object.keys(G).forEach(n => getCycle(G, n, []))
}
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:[]
})
console.log('ok')
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:['p1']
})

现在这不是最有效的方法，因为我们：

• 在作为数组而不是集合的路径上找到（同义O（k）代替O（1）]
• 即使已经访问过顶点，也要重新访问它们

出于可读性考虑，在优化后的版本下方？

function getCycle (G, n, path, visited) {
  if (path.has(n)) {
    const v = [...path]
    throw `cycle ${v.slice(v.indexOf(n)).concat(n).join('<-')}`
  }
  visited.add(n)
  path.add(n)
  return G[n].forEach(next => getCycle(G, next, new Set(path), visited))
}
function validate (G) {
  const visited = new Set()
  Object.keys(G).forEach(n => {
    if (visited.has(n)) return
    getCycle(G, n, new Set(), visited)
  })
}


validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:[]
})
console.log('ok')
validate({
  p1:['p2','p3','p4'],
  p2:['p3'],
  p3:['p0'],
  p0:[],
  p4:['p1']
})