如何基于自定义dependsOn字段对任务对象数组排序

问题描述 #

我有一个包含任务及其依赖的对象数组，原始数据如下：

let taskArray = [
  { taskId: 'SR-1', dependsOn: 'SR-2'}, 
  { taskId: 'SR-2', dependsOn: 'SR-5'}, 
  { taskId: 'SR-3', dependsOn: null},
  { taskId: 'SR-4', dependsOn: 'SR-3'},
  { taskId: 'SR-5', dependsOn: null},
  { taskId: 'SR-6', dependsOn: 'SR-2'}
]

期望处理后得到按依赖关系排序的数组：无依赖（dependsOn为null）的任务顺序可任意，但有依赖的任务必须排在其依赖任务之后，目标结果示例：

let sequencedArray = [
  { taskId: 'SR-3', dependsOn: null},
  { taskId: 'SR-5', dependsOn: null},
  { taskId: 'SR-2', dependsOn: 'SR-5'},
  { taskId: 'SR-1', dependsOn: 'SR-2'}, 
  { taskId: 'SR-6', dependsOn: 'SR-2'},
  { taskId: 'SR-4', dependsOn: 'SR-3'},
]

解决方案 #

这个问题本质是有向无环图（DAG）的拓扑排序，通过以下步骤实现：

步骤1：构建任务映射与依赖关系结构 #

先将任务数组转换为便于快速查询的映射结构，同时构建反向依赖图（记录每个任务被哪些任务依赖），并统计每个任务的入度（未完成的前置依赖数量）。

步骤2：执行拓扑排序 #

1. 先将所有入度为0的独立任务（dependsOn为null）加入处理队列。
2. 依次取出队列中的任务加入结果数组，再遍历该任务的所有依赖者，将它们的入度减1；当某个任务的入度变为0时，说明其前置依赖已全部完成，将其加入队列。
3. 重复操作直到队列为空，即可得到符合要求的排序结果。

代码实现 #

function sortTasksByDependency(taskArray) {
  // 任务映射：通过taskId快速获取任务对象
  const taskMap = {};
  // 反向依赖图：key为被依赖的taskId，value为依赖它的任务ID列表
  const reverseDependents = {};
  // 入度统计：记录每个任务的未完成前置依赖数量
  const inDegree = {};

  // 初始化数据结构
  taskArray.forEach(task => {
    taskMap[task.taskId] = task;
    inDegree[task.taskId] = task.dependsOn ? 1 : 0;

    if (task.dependsOn) {
      if (!reverseDependents[task.dependsOn]) {
        reverseDependents[task.dependsOn] = [];
      }
      reverseDependents[task.dependsOn].push(task.taskId);
    }
  });

  // 初始化队列：所有无依赖的任务
  const queue = taskArray.filter(task => task.dependsOn === null).map(task => task.taskId);
  const result = [];

  while (queue.length > 0) {
    const currentTaskId = queue.shift();
    result.push(taskMap[currentTaskId]);

    // 更新当前任务的所有依赖者的入度
    const dependents = reverseDependents[currentTaskId] || [];
    dependents.forEach(depTaskId => {
      inDegree[depTaskId]--;
      if (inDegree[depTaskId] === 0) {
        queue.push(depTaskId);
      }
    });
  }

  return result;
}

// 测试示例
const taskArray = [
  { taskId: 'SR-1', dependsOn: 'SR-2'}, 
  { taskId: 'SR-2', dependsOn: 'SR-5'}, 
  { taskId: 'SR-3', dependsOn: null},
  { taskId: 'SR-4', dependsOn: 'SR-3'},
  { taskId: 'SR-5', dependsOn: null},
  { taskId: 'SR-6', dependsOn: 'SR-2'}
];

console.log(sortTasksByDependency(taskArray));

代码说明 #

• taskMap：避免多次遍历原始数组，提升查询效率。
• reverseDependents：方便在处理完前置任务后，快速找到所有需要更新依赖状态的后续任务。
• inDegree：通过入度变化判断任务是否满足执行条件（前置依赖全部完成）。
• 队列处理：保证每次处理的都是当前可执行的任务，最终输出的数组完全符合依赖排序要求。

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