本文介绍如何对具有依赖关系（dependsOn）的任务对象数组进行拓扑排序，确保每个任务在其所依赖的任务之后出现；支持多根节点（dependsOn: null），并提供可直接运行的深度优先遍历（DFS）实现方案。
本文介绍如何对具有依赖关系（`dependson`）的任务对象数组进行拓扑排序，确保每个任务在其所依赖的任务之后出现；支持多根节点（`dependson: null`），并提供可直接运行的深度优先遍历（dfs）实现方案。
在构建工作流引擎、任务调度系统或依赖解析器时，常需将一组存在先后依赖关系的对象（如任务、模块、构建步骤）按执行顺序排列。本例中，每个任务通过 dependsOn 字段声明其前置依赖（值为另一任务的 taskId 或 null 表示无依赖），目标是生成一个满足所有依赖约束的线性序列——即典型的有向无环图（DAG）拓扑排序问题。
核心思路是将任务关系建模为森林（多棵树）：所有 dependsOn: null 的任务为根节点，其余任务作为子节点挂载到对应父节点下。随后采用前序深度优先遍历（NLR），先访问根节点，再递归访问其全部后代，从而自然保证“依赖先行”。
以下是完整、健壮的实现：
function topologicalSortByDependsOn(tasks) {
// Step 1: 构建依赖索引映射 —— key 为父 taskId（含 null），value 为子任务数组
const dependencyMap = tasks.reduce((map, task) => {
const parentKey = task.dependsOn;
if (!map[parentKey]) map[parentKey] = [];
map[parentKey].push(task);
return map;
}, {});
// Step 2: DFS 前序遍历（从所有根节点开始）
const result = [];
function dfs(nodes) {
for (const node of nodes) {
result.push(node); // 先加入当前节点（保证依赖项在前）
const children = dependencyMap[node.taskId] || [];
dfs(children); // 再递归处理其所有直接子任务
}
}
// 启动遍历：从所有 dependsOn === null 的根任务开始
const rootTasks = dependencyMap[null] || [];
dfs(rootTasks);
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(topologicalSortByDependsOn(taskArray));
// 输出顺序符合预期：
// SR-3 → SR-4；SR-5 → SR-2 → SR-1/SR-6（SR-1 与 SR-6 同级，顺序可互换）
✅ 关键说明：
- 该算法隐含假设输入无循环依赖（如 A → B → A）。生产环境建议增加环检测（例如使用 visited/recStack 双标记 DFS），否则将导致无限递归。
- 根节点（dependsOn: null）之间无序，若需固定顺序（如按 taskId 字母序），可在 rootTasks 排序后再传入 dfs。
- 时间复杂度为 O(n + e)（n=任务数，e=依赖边数），空间复杂度 O(n + e)（用于存储映射与递归栈）。
此方法简洁、高效且易于理解，适用于中小型依赖图；对于超大规模或需动态更新的场景，可进一步引入 Kahn 算法（BFS 版拓扑排序）以支持增量处理与环检测。
