1. DAG 基础概念：有向无环图的定义、拓扑排序原理、DAG 在任务调度中的核心价值

1.1 有向无环图的定义

有向无环图（Directed Acyclic Graph, DAG）是图论中的一种特殊结构，由一组顶点（Vertex）和一组有向边（Directed Edge）组成，且图中不存在任何环路。在任务调度与数据传输领域，DAG 是描述任务依赖关系与执行顺序的数学基础。

1.2 拓扑排序原理

拓扑排序（Topological Sorting）是将 DAG 的所有顶点排成一个线性序列，使得对于每条有向边 (u, v)，u 在序列中都出现在 v 之前。这是 DAG 调度的核心算法基础。

两种经典实现算法：

• Kahn 算法（入度法）：反复移除入度为 0 的顶点，将其加入排序结果，并移除其所有出边。
• DFS 后序法：深度优先遍历，在回溯时将顶点压入栈，最终栈的逆序即为拓扑序。

// Kahn 算法伪代码
function topologicalSort(graph):
    inDegree = computeInDegree(graph)
    queue = [v for v in graph.vertices if inDegree[v] == 0]
    result = []

    while queue is not empty:
        u = queue.dequeue()
        result.append(u)
        for v in graph.outNeighbors(u):
            inDegree[v]--
            if inDegree[v] == 0:
                queue.enqueue(v)

    if len(result) != len(graph.vertices):
        throw "Graph contains a cycle"
    return result

1.3 DAG 在任务调度中的核心价值

DAG 之所以成为任务调度与数据传输的标准建模工具，源于以下四个核心价值：

1. 依赖显式化：任务间的先后关系、数据依赖、资源约束通过有向边清晰表达，消除隐式耦合。
2. 并行度最大化：拓扑排序自动识别无依赖的任务组，调度器可同时调度这些任务，充分利用集群资源。
3. 容错与重试边界：DAG 的每个顶点是独立的失败域，失败任务仅影响其下游，调度器可精确重试或回滚。
4. 可观测性：DAG 结构天然支持执行状态追踪、进度可视化、瓶颈分析。

1.4 DAG 结构示意图

下图展示了一个典型的数据传输 DAG，包含 6 个任务节点和 7 条依赖边，体现分层依赖与并行执行模式：

1.5 拓扑排序与调度顺序

对上述 DAG 执行拓扑排序，可得到多个合法的执行序列。以下表格展示其中一种典型序列及其并行调度策略：

1.6 DAG 与数据传输的天然契合

在数据传输管道中，DAG 的边不仅表示依赖关系，还承载数据语义：

• 数据血缘：每条边记录数据的来源、转换操作与去向，支撑数据溯源与审计。
• 增量传输：DAG 支持部分节点增量执行，仅重新计算变更的上游节点，避免全量重跑。
• 背压传播：当下游节点处理速度低于上游时，DAG 结构允许背压信号沿边反向传播，实现流量控制。