将扁平化依赖关系转换为嵌套树结构教程

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

/**
 * 从数组中排除集合中存在的元素。
 * @param {Array} arr - 原始数组。
 * @param {Set} omitSet - 包含要排除元素的集合。
 * @returns {Array} - 过滤后的数组。
 */
const exclude = (arr, omitSet) => arr.filter(val => !omitSet.has(val));

/**
 * 找出数组中的重复元素并返回一个包含这些重复元素的集合。
 * @param {Array} arr - 原始数组。
 * @returns {Set} - 包含重复元素的集合。
 */
const duplicateSet = (arr) => {
    // 使用一个Set来跟踪已经“见过”的元素。
    // 如果一个元素被再次“见到”，说明它是重复的。
    const seen = new Set();
    const duplicates = new Set();
    for (const val of arr) {
        if (seen.has(val)) {
            duplicates.add(val);
        } else {
            seen.add(val);
        }
    }
    return duplicates;
};

/**
 * 将扁平化的依赖关系对象转换为嵌套的树状结构。
 * @param {Object<string, string[]>} data - 键是项目，值是其依赖项列表的对象。
 * @returns {Object} - 嵌套的树状结构。
 */
function toNested(data) {
    // 用于存储已构建的节点，避免重复计算和处理循环依赖
    const nodes = {};

    // 收集所有作为依赖项出现的子节点
    const descendants = Object.values(data).flat();

    // 识别具有多个父级的依赖项（即在descendants中出现多次的元素）
    const withMultipleParents = duplicateSet(descendants);

    // 识别只被一个父级依赖的依赖项
    const withSingleParents = new Set(exclude(descendants, withMultipleParents));

    // 确定顶层节点：
    // 1. 那些不作为任何依赖项出现的键（即没有父级）
    // 2. 那些具有多个父级的依赖项（根据规则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] = {};

        // 遍历当前节点的依赖项（子节点）
        for (const child of data[key] ?? []) { // 使用 ?? [] 处理没有依赖项的情况
            // 只有当子节点是单一父级依赖时，才将其嵌套到当前节点下
            if (withSingleParents.has(child)) {
                nodes[key][child] = dfs(child);
            }
            // 多父级依赖的子节点不会在此处嵌套，它们会在withNoParents中作为顶层节点处理
        }
        return nodes[key];
    }

    // 从所有顶层节点开始构建最终的树结构
    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": {
    "f": {},
    "q": {}
  },
  "p": {
    "o": {}
  },
  "c": {
    "d": {}
  },
  "e": {}
}