📚 课程目录第2章 DAG基础理论

2. DAG 基础理论：有向无环图定义、拓扑排序原理、关键路径算法

在分布式任务调度系统中，DAG（有向无环图）是描述任务依赖关系的核心数学模型。理解 DAG 的定义、拓扑排序原理以及关键路径算法，是设计高效调度引擎的理论基石。本节将系统性地阐述这三个核心概念，并辅以图示与代码示例，帮助您建立扎实的理论框架。

2.1 有向无环图（DAG）定义与核心要素

DAG 是一种特殊的有向图，其中不存在任何有向环路。在任务调度场景中，每个节点代表一个任务单元，每条有向边表示任务之间的依赖关系（即前驱任务完成后，后继任务才能开始执行）。

  核心定义： 一个 DAG 由顶点集合 V 和有向边集合 E 组成，且对于任意顶点 v ∈ V，不存在一条从 v 出发经过若干条有向边后回到 v 的路径。

要素	符号	调度含义	示例
顶点（Vertex）	V = {v₁, v₂, …, vₙ}	任务单元（如数据清洗、模型训练）	Task_A, Task_B
有向边（Directed Edge）	E ⊆ V × V	依赖关系（前驱→后继）	Task_A → Task_B
入度（In-degree）	deg⁻(v)	指向该任务的直接前驱数量	入度为 0 表示无依赖
出度（Out-degree）	deg⁺(v)	该任务触发的直接后继数量	出度为 0 表示终端任务
源点（Source）	deg⁻(v) = 0	可立即启动的起始任务	数据采集任务
汇点（Sink）	deg⁺(v) = 0	无后继的最终任务	结果输出任务

实践要点： 在构建任务 DAG 时，务必确保图中不存在环路。常见的环路检测方法包括拓扑排序（若无法完成所有节点排序，则存在环）和 DFS 回溯标记法。

2.2 拓扑排序原理与实现

拓扑排序是对 DAG 中所有顶点的一种线性排序，使得对于每一条有向边 u → v，顶点 u 在排序中都出现在顶点 v 之前。在任务调度中，拓扑排序直接决定了任务的执行顺序。

2.2.1 Kahn 算法（基于入度）

Kahn 算法通过维护一个入度为 0 的顶点队列，逐步移除顶点及其出边，直到所有顶点都被处理。该算法的时间复杂度为 O(V + E)，空间复杂度为 O(V)。

// Kahn 算法伪代码
function topologicalSortKahn(graph):
    inDegree = 计算每个顶点的入度
    queue = 所有入度为 0 的顶点
    result = []

    while queue 不为空:
        vertex = queue.dequeue()
        result.append(vertex)

        for each neighbor in graph[vertex]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.enqueue(neighbor)

    if result.length != graph.vertexCount:
        throw "图中存在环路，无法完成拓扑排序"
    return result

2.2.2 DFS 后序法

基于深度优先搜索（DFS）的拓扑排序利用递归后序遍历：当某个顶点的所有后继顶点都被访问完毕后，将该顶点压入栈中。最终栈的逆序即为拓扑排序结果。

// DFS 后序法伪代码
function topologicalSortDFS(graph):
    visited = 空集合
    stack = []

    function dfs(vertex):
        visited.add(vertex)
        for each neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.push(vertex)  // 后序入栈

    for each vertex in graph:
        if vertex not in visited:
            dfs(vertex)

    return stack.reverse()  // 栈的逆序

对比维度	Kahn 算法	DFS 后序法
核心思想	贪心移除入度为 0 的顶点	递归后序压栈
数据结构	队列 + 入度数组	栈 + 访问标记
环路检测	结果长度 < 顶点总数时存在环	递归过程中遇到灰色节点（正在访问）时存在环
适用场景	需要实时输出排序结果、动态 DAG	需要同时进行其他图遍历操作
稳定性	稳定，入度队列可控制同层顺序	依赖递归深度，大图可能栈溢出

常见陷阱： 拓扑排序仅适用于 DAG。如果图中存在环路，Kahn 算法会在队列为空时仍有未处理顶点；DFS 法会在递归中检测到回边。生产环境中，建议在构建 DAG 后立即执行拓扑排序以验证无环。

2.3 关键路径算法（CPM）

关键路径（Critical Path）是 DAG 中从源点到汇点的最长路径，决定了整个任务调度的最短完成时间。关键路径上的任务称为关键任务，任何关键任务的延迟都会直接导致整体工期延长。

2.3.1 核心概念

最早开始时间（ES, Earliest Start）： 任务可以开始的最早时刻，等于所有前驱任务最早完成时间的最大值。
最早完成时间（EF, Earliest Finish）： EF = ES + 任务持续时间。
最晚开始时间（LS, Latest Start）： 在不影响整体工期的前提下，任务必须开始的最晚时刻。
最晚完成时间（LF, Latest Finish）： LF = LS + 任务持续时间，或等于所有后继任务最晚开始时间的最小值。
总时差（TF, Total Float）： TF = LS - ES = LF - EF。总时差为 0 的任务即为关键任务。

2.3.2 算法步骤

正向遍历（Forward Pass）： 从源点开始，按拓扑排序顺序计算每个任务的 ES 和 EF。源点的 ES = 0。
反向遍历（Backward Pass）： 从汇点开始，按拓扑排序的逆序计算每个任务的 LS 和 LF。汇点的 LF = 其 EF。
识别关键路径： 找出所有 TF = 0 的任务，这些任务构成的路径即为关键路径。

// 关键路径算法核心逻辑（伪代码）
function criticalPath(graph, durations):
    topoOrder = topologicalSortKahn(graph)
    // 正向遍历
    for each v in topoOrder:
        ES[v] = max(EF[u] for u in predecessors[v])  // 默认为 0
        EF[v] = ES[v] + durations[v]
    // 反向遍历
    for each v in reverse(topoOrder):
        LF[v] = min(LS[w] for w in successors[v])    // 默认为 EF[v]
        LS[v] = LF[v] - durations[v]
    // 计算总时差
    for each v:
        TF[v] = LS[v] - ES[v]
    // 提取关键路径
    criticalTasks = [v for v in graph if TF[v] == 0]
    return criticalTasks

  工程意义： 在分布式任务调度中，关键路径算法用于识别瓶颈任务。调度引擎可以优先保障关键任务的资源分配，并在关键任务发生延迟时触发告警或动态调整策略。

2.3.3 关键路径示例

假设一个包含 5 个任务的 DAG，各任务持续时间如下：A(3), B(2), C(4), D(1), E(5)。依赖关系为：A→B, A→C, B→D, C→D, D→E。

任务	持续时间	ES	EF	LS	LF	TF	是否关键
A	3	0	3	0	3	0	是
B	2	3	5	4	6	1	否
C	4	3	7	3	7	0	是
D	1	7	8	7	8	0	是
E	5	8	13	8	13	0	是

关键路径为：A → C → D → E，总工期为 13 个时间单位。任务 B 有 1 个时间单位的浮动，不属于关键路径。