2. DAG 基础概念：有向无环图定义、顶点与边、入度与出度、拓扑排序核心思想

在构建分布式任务调度系统之前，必须彻底理解 DAG（有向无环图）这一核心数据结构。DAG 不仅是任务依赖关系的数学表达，更是整个调度引擎的骨架。本节将系统性地拆解 DAG 的四个基本概念：定义、顶点与边、入度与出度、拓扑排序，并揭示它们如何映射到实际的任务调度场景中。

2.1 有向无环图（DAG）定义

DAG 是一种特殊的有向图，它满足两个关键约束：有向 和 无环。

• 有向（Directed）：图中的每条边都具有明确的方向，表示从一个顶点指向另一个顶点。在任务调度中，方向代表依赖关系的流向——前驱任务完成后才能启动后继任务。
• 无环（Acyclic）：图中不存在任何环路（Cycle），即无法从某个顶点出发，沿着有向边回到该顶点。无环性是保证调度可终止、无死锁的前提。

2.2 顶点（Vertex）与边（Edge）

DAG 由两个基本元素构成：顶点和边。在任务调度上下文中，它们有明确的语义映射。

边的方向性至关重要：A → B 表示 A 是 B 的前驱（Predecessor），B 是 A 的后继（Successor）。调度器必须保证所有前驱任务成功完成后，才能调度后继任务。

2.3 入度（In-Degree）与出度（Out-Degree）

入度和出度是描述顶点在 DAG 中连接关系的两个关键度量，它们直接决定了任务的调度优先级和并行度。

• 入度（In-Degree）：指向该顶点的边的数量。在调度中，入度表示一个任务有多少个直接前驱依赖。入度为 0 的任务是可立即调度的任务。
• 出度（Out-Degree）：从该顶点出发的边的数量。出度表示一个任务有多少个直接后继任务。出度高的任务往往是数据分发的关键节点。

2.4 拓扑排序（Topological Sorting）核心思想

拓扑排序是将 DAG 中的所有顶点排列成一个线性序列，使得对于每一条有向边 U → V，顶点 U 在序列中都出现在顶点 V 之前。这个序列定义了任务的合法执行顺序。

拓扑排序的核心算法——Kahn 算法——正是基于入度概念实现的：

1. 初始化：计算所有顶点的入度，将所有入度为 0 的顶点加入队列。
2. 迭代处理：从队列中取出一个顶点，将其加入拓扑序列；然后遍历该顶点的所有后继，将每个后继的入度减 1；如果某个后继的入度变为 0，则将其加入队列。
3. 终止条件：当队列为空时，如果拓扑序列中的顶点数等于 DAG 的总顶点数，则排序成功；否则说明图中存在环。

// Kahn 算法伪代码
function topologicalSort(graph):
    inDegree = computeInDegree(graph)   // 计算所有顶点入度
    queue = new Queue()
    for each vertex v in graph:
        if inDegree[v] == 0:
            queue.enqueue(v)            // 入度为 0 的顶点入队

    result = []
    while queue is not empty:
        u = queue.dequeue()
        result.append(u)
        for each successor v of u:
            inDegree[v]--
            if inDegree[v] == 0:
                queue.enqueue(v)

    if result.length != graph.vertexCount:
        throw "Cycle detected: DAG contains a cycle"
    return result

2.5 DAG 结构与调度映射关系

下面的 SVG 图展示了 DAG 的核心概念及其在任务调度中的映射关系，包括顶点、边、入度、出度以及拓扑排序的生成过程。

2.6 入度驱动的调度执行流程

下图展示了调度器如何利用入度机制，将 DAG 拓扑排序转化为实际的任务执行流程。这是分布式调度引擎的核心运行时逻辑。

2.7 关键概念总结