从依赖对象构建无环层级树结构：JavaScript实现深度解析

{
  'a': ['b', 'q'],
  'b': ['c', 'f'],
  'c': ['d'],
  'p': ['o'],
  'o': [],
  "d": [],
  'e': ['c'],
  "q": []
}

{
  'a': {
    'b': {
      "f": {}
    },
    'q': {}
  },
  "p": {
    'o': {}
  },
  "c": { // 注意：'c' 最初会被 'b' 依赖，但因为它也被 'e' 依赖（多父级），所以它被提升到顶层。
    "d": {}
  },
  "e": {} // 'e' 没有父级，因此也是顶层。
}

/**
 * 从数组中排除Set中包含的元素
 * @param {Array<string>} arr - 输入数组
 * @param {Set<string>} omitSet - 包含要排除元素的Set
 * @returns {Array<string>} 过滤后的数组
 */
const exclude = (arr, omitSet) => arr.filter(val => !omitSet.has(val));

/**
 * 找出数组中的重复元素并返回一个Set
 * @param {Array<string>} arr - 输入数组
 * @returns {Set<string>} 包含重复元素的Set
 */
const duplicateSet = (arr) =>
    new Set(arr.filter(function (val) {
        // 使用Set的delete方法来检测重复，第一次遇到时删除，第二次遇到时delete返回false，表示是重复项
        return !this.delete(val);
    }, new Set(arr))); // 初始Set用于追踪已见的元素

function toNested(data) {
    const nodes = {}; // 用于存储已构建的节点，避免重复计算和处理循环引用
    const descendants = Object.values(data).flat(); // 收集所有依赖项（子节点）

    // 1. 识别具有多个父级的依赖项 (共享依赖)
    const withMultipleParents = duplicateSet(descendants);

    // 2. 识别具有单个父级的依赖项
    // 从所有子节点中排除掉具有多个父级的节点
    const withSingleParents = new Set(exclude(descendants, withMultipleParents));

    // 3. 确定最终的顶层节点
    // 顶层节点包括：
    //   a. 那些在原始数据键中存在，但未作为任何其他项目的子节点出现的（真正的根节点）
    //   b. 那些具有多个父级的依赖项（根据规则3，它们被提升到顶层）
    const withNoParents = [...exclude(Object.keys(data), withSingleParents), ...withMultipleParents];

    /**
     * 深度优先搜索函数，递归构建子树
     * @param {string} key - 当前要构建的节点键
     * @returns {Object} 构建好的子树对象
     */
    function dfs(key) {
        // 如果节点已经构建过，直接返回，这有助于处理潜在的循环引用和优化性能
        if (nodes[key]) return nodes[key];

        // 初始化当前节点为一个空对象
        nodes[key] = {};

        // 遍历当前节点的所有直接子依赖项
        // 使用 `data[key] ?? []` 处理 key 不存在或其值为 null/undefined 的情况
        for (const child of data[key] ?? []) {
            // 只有当子节点是“单父级依赖”时，才将其嵌套在当前节点下
            // 具有多个父级的子节点会作为顶层节点处理，不会被嵌套
            if (withSingleParents.has(child)) {
                nodes[key][child] = dfs(child); // 递归构建子节点
            }
        }
        return nodes[key];
    }

    // 遍历所有顶层节点，并为它们启动DFS构建过程
    // 使用 Object.fromEntries 将键值对数组转换为最终对象
    return Object.fromEntries(withNoParents.map(key => [key, dfs(key)]));
}

const data = {
    'a': ['b', 'q'],
    'b': ['c', 'f'],
    'c': ['d'],
    'p': ['o'],
    'o': [],
    "d": [],
    'e': ['c'],
    "q": []
};

console.log(toNested(data));

{
  "a": {
    "b": {
      "f": {}
    },
    "q": {}
  },
  "p": {
    "o": {}
  },
  "c": {
    "d": {}
  },
  "e": {}
}