如何更优实现JavaScript中带依赖关系的任务执行函数

我有一组带依赖关系的任务列表：

let tasks = {
  a: {
    job: function () {
      console.log('Tasks A running')
    },
    dependency: ['c', 'b'],
  },
  b: {
    job: function () {
      console.log('Tasks B running')
    },
    dependency: [],
  },
  c: {
    job: function () {
      console.log('Tasks C running')
    },
    dependency: ['b'],
  },
}

执行逻辑要求：先运行无依赖的任务（本例为b），待其完成后运行依赖b的c，最后运行a。

我自行实现的方案如下：

function runTasks(tasks) {
  while (Object.keys(tasks).length) {
    for (let [key, { dependency, job }] of Object.entries(tasks)) {
      if (dependency.length === 0) {
        job()
        deleteAllOccurance(tasks, key)
        delete tasks[key]
      }
    }
  }
}

function deleteAllOccurance(tasks, name) {
  for (let [key, { dependency }] of Object.entries(tasks)) {
    tasks[key].dependency = dependency.filter((x) => x !== name)
  }
}
runTasks(tasks)

该方案虽能正常运行，但存在两点不足：

• 篡改了原始tasks对象；
• 每次需遍历所有任务的依赖列表删除指定项，性能效率较低。

优化方案：基于拓扑排序（入度统计） #

我们可以通过统计每个任务的入度（即未完成的依赖数量）来实现，全程不修改原对象，且避免重复遍历所有依赖列表：

function runTasksOptimized(tasks) {
  // 1. 统计入度并构建依赖映射：记录哪些任务依赖当前任务
  const inDegree = {};
  const dependents = {};
  const taskKeys = Object.keys(tasks);

  // 初始化入度与依赖映射容器
  taskKeys.forEach(key => {
    inDegree[key] = tasks[key].dependency.length;
    dependents[key] = [];
  });

  // 填充依赖映射
  taskKeys.forEach(key => {
    tasks[key].dependency.forEach(dep => {
      dependents[dep].push(key);
    });
  });

  // 2. 筛选初始无依赖（入度为0）的任务
  const queue = taskKeys.filter(key => inDegree[key] === 0);

  // 3. 执行任务并更新后续任务入度
  while (queue.length > 0) {
    const currentKey = queue.shift();
    // 执行当前任务
    tasks[currentKey].job();

    // 更新所有依赖当前任务的后续任务入度
    dependents[currentKey].forEach(depKey => {
      inDegree[depKey]--;
      // 入度为0时，加入执行队列
      if (inDegree[depKey] === 0) {
        queue.push(depKey);
      }
    });
  }
}

// 调用优化后的函数，不会修改原始tasks对象
runTasksOptimized(tasks);

优化点说明 #

• 不修改原对象：所有统计数据（入度、依赖映射）均为新创建的结构，完全保留原始tasks的完整性；
• 性能提升：仅需两次遍历完成初始化，后续仅更新直接关联任务的入度，时间复杂度从O(n²)优化为O(n + m)（n为任务数，m为依赖关系总数）；
• 逻辑清晰：基于拓扑排序的标准实现，符合依赖任务执行的经典算法思路，可读性与可维护性更强。

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