如何对具有依赖关系的对象数组进行拓扑排序（基于 xid 的层级依赖）-js教程-PHP中文网

如何对具有依赖关系的对象数组进行拓扑排序（基于 xid 的层级依赖）

本文介绍一种基于树结构建模与深度优先遍历（DFS）的算法，用于对含 xid 依赖关系的表单对象数组进行正确排序：无 xid 的“入口项”在前，有 xid 的“跳转目标项”严格置于其引用源之后，支持多层嵌套依赖（如 A → B → C）。

本文介绍一种基于树结构建模与深度优先遍历（DFS）的算法，用于对含 `xid` 依赖关系的表单对象数组进行正确排序：无 `xid` 的“入口项”在前，有 `xid` 的“跳转目标项”严格置于其引用源之后，支持多层嵌套依赖（如 A → B → C）。

在构建多步骤交互式表单（如问卷、向导流程）时，常需按逻辑顺序展示问题节点。典型场景是：某个 radio 选项的 step 字段指向另一个具有 xid 的问题，而该 xid 对应的问题必须出现在引用它的节点之后——这本质上是一种有向依赖图的线性化问题，而非简单比较排序。直接使用 Array.prototype.sort() 无法解决，因其不满足传递性与稳定性要求；而原生循环移动法（如 splice 插入）易因索引偏移导致错序或死循环。

我们采用「建树 + DFS 扁平化」两阶段策略，清晰、健壮且易于扩展：

✅ 第一阶段：构建依赖树（`buildTree`）

建立哈希索引：遍历一次原始数组，用 xid 为 key 缓存所有带 xid 的对象（lookup[xid] = item），实现 O(1) 查找。
提取子节点关系：对每个对象，扫描其 options 数组中所有含 step.xid 的项，收集 xid 列表，并通过 lookup 映射为实际子节点对象（item.children = [...]）。
识别根节点：仅 xid 为 undefined 或 null 的对象视为根（即用户流程起点），加入 result 数组。
可选优化：根节点按子节点数量升序排列（子节点少者优先），使简单分支前置，提升可读性。

✅ 第二阶段：深度优先扁平化（`flattenTree`）

递归执行 DFS：对每个根节点，先推入结果数组，再对其 children 逐个递归处理。
清理副作用：遍历完成后删除临时添加的 children 属性，保持输出对象纯净。

以下是完整可运行实现：

function sortDependentQuestions(items) {
  const lookup = {};

  // Step 1: Build xid → item lookup map
  items.forEach(item => {
    if (item.xid !== undefined && item.xid !== null) {
      lookup[item.xid] = item;
    }
  });

  // Step 2: Attach children & collect roots
  const roots = [];
  items.forEach(item => {
    // Extract valid step.xid references
    const childXids = (item.options || [])
      .filter(opt => opt.step && opt.step.xid)
      .map(opt => opt.step.xid);

    // Resolve to actual objects; ignore missing xid (dangling refs)
    item.children = childXids.map(xid => lookup[xid]).filter(Boolean);

    // Root: no xid at top level
    if (item.xid === undefined || item.xid === null) {
      roots.push(item);
    }
  });

  // Optional: Sort roots by dependency depth (shallow first)
  roots.sort((a, b) => a.children.length - b.children.length);

  // Step 3: DFS flatten
  const result = [];
  function dfs(node) {
    result.push(node);
    node.children?.forEach(dfs);
  }
  roots.forEach(dfs);

  // Clean up temporary property
  result.forEach(item => delete item.children);

  return result;
}

// ✅ 使用示例
const input = [
  {
    type: 'radio',
    text: "Looking for online",
    options: [
      { text: "Yes", step: { text: "Select City", xid: 1 } },
      { text: "No" }
    ]
  },
  { type: "single", text: "First Name" },
  { type: "single", text: "Last Name" },
  {
    type: 'radio',
    text: "Select Area",
    xid: 2,
    options: [{ text: "Yes" }, { text: "No" }]
  },
  {
    type: 'radio',
    text: "Select City",
    xid: 1,
    options: [
      { text: "Mumbai", step: { text: "Select Area", xid: 2 } },
      { text: "Delhi" }
    ]
  }
];

console.log(sortDependentQuestions(input));
// 输出顺序：First Name → Last Name → Looking for online → Select City → Select Area

⚠️ 注意事项与边界处理

悬空引用（Dangling Reference）：若 step.xid 在数组中不存在对应 xid 对象，lookup[xid] 为 undefined，.filter(Boolean) 自动剔除，不影响排序。
循环依赖：当前实现不检测环（如 A → B → A）。生产环境建议在 buildTree 后加入环检测（如 DFS 状态标记：unvisited/visiting/visited）。
重复 xid：lookup 覆盖机制取最后一个同 xid 对象，确保行为确定。如有业务要求唯一性，应在上游校验。
非 radio 类型兼容：算法不依赖 type 字段，只要对象含 options 和 step.xid 即可参与依赖解析（如 select、button 等）。