2. DAG的核心要素
好，咱们正式开始啃DAG。说实话，我第一次接触DAG是在做数据流水线调度的时候。当时有个任务总跑不对，依赖关系乱成一锅粥。后来我把整个流程画成了一张图，才恍然大悟——原来这就是DAG啊。
DAG的全称是有向无环图。名字听着唬人，拆开看就三个词：有向、无环、图。咱们一个一个说。
2.1 节点（Vertex）与边（Edge）
图的基本组成单位就两个东西：节点和边。节点就是图中的圆圈或方框，代表一个实体。边就是连接节点的线，代表关系。
在DAG里，边是有方向的。你想想看，如果A指向B，意思就是A完成后才能开始B。这个方向很关键，它决定了整个流程的执行顺序。
节点：表示一个任务、一个状态或一个数据实体。
边：表示依赖关系或数据流向，箭头从依赖方指向被依赖方。
举个例子。假设你要做一顿饭：
- 节点：洗菜、切菜、烧水、煮面、炒菜、装盘
- 边：洗菜 → 切菜（先洗后切），烧水 → 煮面（水开了才能下面）
你看，这就是一个简单的DAG。每个节点代表一个动作，每条边代表先后顺序。
我在项目中遇到过一种情况：有人把依赖关系画反了。A依赖B，结果箭头从A指向B。嗯，这里要注意——箭头方向代表的是流向，不是依赖。我个人习惯用「谁先执行，箭头就指向谁」来记忆。
2.2 入度与出度
这两个概念是理解DAG的关键。说白了，就是数一数每个节点有多少条边进来、多少条边出去。
| 概念 | 定义 | 通俗理解 |
|---|---|---|
| 入度 | 指向该节点的边的数量 | 有多少个前置任务 |
| 出度 | 从该节点出发的边的数量 | 有多少个后续任务 |
入度为0的节点，意味着它没有前置依赖，可以最先执行。出度为0的节点，意味着它没有后续任务，通常是整个流程的终点。
小技巧：在调度系统里，入度为0的节点就是「起跑线」。我每次做任务编排，第一件事就是找出所有入度为0的节点，它们就是整个DAG的入口。
我曾经踩过一个坑：有个任务一直不执行，排查了半天才发现，它的入度算错了。代码里把一条依赖重复加了两次，导致入度比实际多1，调度器一直等那个「不存在的依赖」完成。从那以后，我每次计算入度都会手动验证一遍。
2.3 拓扑排序
拓扑排序，说白了就是给DAG里的所有节点排个队，排完之后，每条边的起点都在终点前面。
你想想看，如果A → B → C，那么拓扑排序的结果必须是A在B前面，B在C前面。不能出现C在A前面的情况，否则就乱套了。
拓扑排序的经典算法有两种：
- Kahn算法：基于入度，每次取出入度为0的节点
- DFS后序遍历：深度优先搜索，然后反转结果
我个人更常用Kahn算法，因为它直观，而且能顺便检测环。
// Kahn算法伪代码
function topologicalSort(graph):
inDegree = 计算每个节点的入度
queue = 所有入度为0的节点
result = []
while queue不为空:
node = queue.pop()
result.append(node)
for neighbor in graph[node]:
inDegree[neighbor]--
if inDegree[neighbor] == 0:
queue.push(neighbor)
if result.length != 节点总数:
throw "图中存在环，无法拓扑排序"
return result这段代码的逻辑其实很简单：先把所有「没人依赖」的节点拿出来，然后每拿一个，就把它指向的节点的入度减1。如果某个节点的入度变成0了，说明它的前置任务都完成了，可以加入队列。
注意：拓扑排序只适用于DAG。如果图里有环，拓扑排序会失败。Kahn算法最后检查result的长度，如果小于节点总数，说明有环。这个检查一定要做，我见过有人忘了加，结果调度器死循环了。
拓扑排序的结果不唯一。同一个DAG可能有多个合法的拓扑序列。比如A → B和A → C，B和C之间没有依赖，那么B在C前面或C在B前面都是合法的。
2.4 一张图看懂DAG核心要素
下面这张SVG图把节点、边、入度、出度和拓扑排序串在了一起。你可以对照着看，理解会更直观。
你看这张图，A的入度是0，所以它最先执行。D的入度是2，必须等B和C都完成才能执行。拓扑排序的结果里，A永远在B和C前面，B和C都在D前面。
这就是DAG的核心逻辑。搞懂了节点、边、入度、出度和拓扑排序，你就掌握了DAG的骨架。后面咱们聊的调度、依赖管理、数据血缘，全都是在这个骨架上长出来的。