如何检测JavaScript对象数组中的循环引用（自引用/间接循环）

给定如下JavaScript对象数组：

const a = [
  {id:1, parentId:2},
  {id:2, parentId:3},
  {id:3, parentId:4},
  {id:4, parentId:1},
  {id:5, parentId:5}
];

需要检测数组中是否存在直接自引用（如id=5的对象parentId指向自身）或间接循环引用（如1→2→3→4→1的闭环），要求返回是否存在循环，同时输出对应的循环路径。

实现思路 #

最优方案是通过哈希映射快速查找父节点+路径追踪检测循环，核心逻辑：

• 先构建id到parentId的映射表，将父节点查找复杂度降到O(1)
• 用visited集合记录已处理的节点，避免重复遍历
• 对每个未处理节点，追踪当前遍历路径：若路径中出现重复节点，说明找到闭环；若节点指向自身，直接判定为自引用循环

代码实现 #

function detectCycles(nodes) {
  // 构建id到parentId的映射，O(n)时间
  const idToParent = new Map();
  nodes.forEach(node => idToParent.set(node.id, node.parentId));
  
  const visited = new Set();
  const cycles = [];

  for (const node of nodes) {
    const currentId = node.id;
    if (visited.has(currentId)) continue;

    const path = new Map(); // 记录当前路径：key=节点id，value=路径中的索引
    let current = currentId;

    while (true) {
      // 节点已被全局处理过，终止当前路径追踪
      if (visited.has(current)) {
        // 当前节点在当前路径中，说明找到闭环
        if (path.has(current)) {
          const cycle = Array.from(path.keys()).slice(path.get(current));
          cycle.push(current); // 补上闭环终点，形成完整循环
          cycles.push(cycle);
        }
        break;
      }

      // 当前节点不在映射中（边界处理，题目场景可忽略）
      if (!idToParent.has(current)) break;

      // 检测到直接自引用
      if (current === idToParent.get(current)) {
        cycles.push([current]);
        visited.add(current);
        break;
      }

      // 当前节点已在当前路径中，找到间接循环
      if (path.has(current)) {
        const cycle = Array.from(path.keys()).slice(path.get(current));
        cycle.push(current);
        cycles.push(cycle);
        // 标记路径中所有节点为已访问
        cycle.forEach(id => visited.add(id));
        break;
      }

      // 将当前节点加入路径和已访问集合
      path.set(current, path.size);
      visited.add(current);
      // 移动到父节点
      current = idToParent.get(current);
    }
  }

  // 无循环返回false，否则返回循环结果
  return cycles.length ? { hasCycle: true, cycles } : false;
}

// 测试示例
const result = detectCycles(a);
console.log(result);
// 输出：
// {
//   hasCycle: true,
//   cycles: [[1,2,3,4,1], [5]]
// }

复杂度分析 #

• 时间复杂度：O(n)，每个节点仅被访问一次，所有操作均为常数时间
• 空间复杂度：O(n)，映射表、访问集合和路径追踪的存储均与节点数量线性相关

内容的提问来源于stack exchange，提问作者Mehran Ishanian