一、DAG 基础概念：什么是 DAG、DAG 与树/链表的区别、DAG 在工程中的应用场景

1.1 什么是 DAG？先别急着背定义

DAG，全称 Directed Acyclic Graph，中文叫「有向无环图」。说白了，就是一组节点，节点之间有方向箭头，而且你顺着箭头走，永远走不回起点。

我刚开始接触这个概念时，总觉得它很玄乎。后来在做一个数据管道项目时，发现任务 A 要等任务 B 和 C 完成才能跑，而 B 又依赖 D 和 E……这不就是天然的 DAG 吗？

DAG 有三个核心要素：

• 节点（Vertex）：代表一个独立单元，比如一个计算任务、一个数据源、一个服务。
• 有向边（Directed Edge）：表示依赖关系，箭头从「被依赖者」指向「依赖者」。A → B 表示 B 依赖 A。
• 无环（Acyclic）：不存在一条路径能让你绕回起点。一旦有环，任务就死锁了。

下面这张图，就是一个典型的 DAG：

1.2 DAG 与树、链表的区别

很多初学者会把 DAG 和树搞混。我当年也犯过这个错——以为 DAG 就是多叉树。其实差别很大。

特性	链表	树	DAG
方向	单向或双向	单向（父→子）	单向（依赖方向）
环	可有环（双向链表）	无环	无环
节点连接数	每个节点最多 2 个邻居	每个节点 1 个父节点，多个子节点	每个节点可有多个前驱和多个后继
路径	唯一路径	唯一路径（根到叶）	多条路径可达同一节点
典型用途	队列、栈、列表	文件系统、组织架构	任务编排、数据管道、依赖管理

你想想看，树里一个节点只能有一个父节点。但在 DAG 里，一个任务可以依赖多个上游任务。比如「发布上线」这个任务，可能同时依赖「代码编译」「单元测试」「安全扫描」三个任务都完成。这在树结构里是表达不了的。

1.3 DAG 在工程中的应用场景

DAG 不是理论玩具，它在工程里遍地都是。我列几个最常见的场景：

1.3.1 任务调度与工作流编排

这是 DAG 最经典的应用。比如 Airflow、DolphinScheduler、Temporal 这些调度系统，底层全是 DAG。

我记得在上一家公司，我们用 Airflow 管理几百个数据管道。每天凌晨，数据采集任务先跑，然后并行启动清洗和转换，最后聚合输出报表。一旦某个上游任务失败，下游自动阻塞——这就是 DAG 的天然优势。

1.3.2 数据血缘与溯源

在大数据领域，DAG 用来追踪数据的来龙去脉。比如一个报表字段，它来自哪张表？经过了哪些 ETL 步骤？

我曾经排查过一个数据不一致的问题。顺着 DAG 的血缘关系，发现中间有个转换任务把字段类型搞错了。如果没有 DAG 的血缘图，你根本不知道问题出在哪一环。

1.3.3 编译器的依赖分析

编译器里，源文件之间的依赖关系就是一个 DAG。比如 A.h 被 B.cpp 和 C.cpp 引用，那么 B 和 C 的编译依赖 A 先完成。Makefile、CMake 这些构建工具，本质上就是在解析 DAG。

1.3.4 分布式计算框架

Spark、Flink 这些计算引擎，把计算任务拆成 Stage，Stage 之间构成 DAG。Spark 的 DAG Scheduler 就是专门干这个的——它把 RDD 的依赖关系画成 DAG，然后决定哪些 Stage 可以并行，哪些必须串行。

1.3.5 版本控制与 Git 分支

Git 的提交历史其实就是一个 DAG。每个 commit 是一个节点，parent 指针是边。分支合并会产生多个父节点，但整体上不能有环——你不可能让一个 commit 成为自己的祖先。

1.4 为什么 DAG 这么重要？

说白了，现实世界里的依赖关系，绝大多数都是 DAG。你不可能先做菜再买菜，不可能先部署再测试。DAG 就是用来建模这种「有向无环」的依赖关系的。

我个人习惯，在设计任何需要编排的系统时，第一件事就是画 DAG。把任务画成节点，把依赖画成边，然后检查有没有环。有环？说明设计有问题，需要重新梳理依赖。