Directed Acyclic Graph

释义 Definition（中文）

Directed acyclic graph（DAG，中文常译“有向无环图”）：一种图（graph）结构，其中每条边都有方向（directed），并且不存在任何沿着边的方向走一圈又回到起点的闭环（acyclic）。
它常用于表示依赖关系与先后顺序：只要存在“必须先做 A 才能做 B”的关系，就很适合用 DAG 表达（例如任务调度、版本控制提交历史、编译依赖、数据处理流水线等）。

发音 Pronunciation（IPA）

/dɪˈrɛktɪd eɪˈsaɪklɪk ɡræf/

例句 Examples（EN & ZH）

A task scheduler can represent job dependencies as a directed acyclic graph.
任务调度器可以用有向无环图来表示作业之间的依赖关系。

Because the workflow is a DAG, we can topologically sort the steps and run independent parts in parallel.
因为这个工作流是一个有向无环图，我们可以对步骤进行拓扑排序，并把相互独立的部分并行运行。

词源 Etymology（中文）

• directed 来自 direct（“引导、指向”），强调边具有方向性。
• acyclic 由前缀 a-（“无、非”）+ cyclic（“循环的”）构成，字面即“不成环”。
• graph 源自希腊语词根，和“书写/描画”相关，引申为用点与线来“画出关系”的结构。
  合起来，DAG 就是“方向明确、且不会形成循环的关系图”。

相关词 Related Words

• Acyclic
• Directed
• Graph
• Dependency
• Topological
• Topological Sort
• Partial Order
• Tree
• Cycle
• Vertex
• Edge

文学与著作中的用例 Literary & Notable Works（中文）

由于这是一个偏技术的术语，它更多出现在计算机科学与数学类经典著作中，例如：

• 《Introduction to Algorithms》（Cormen, Leiserson, Rivest, Stein）：以 DAG 讲解拓扑排序、动态规划等核心算法思想。
• 《The Art of Computer Programming》（Donald E. Knuth）：在讨论组合结构与算法时涉及图与有向结构。
• 《Compilers: Principles, Techniques, and Tools》（Aho 等，“龙书”）：编译器中的依赖分析、语法与中间表示常与 DAG/图结构相关。
• 《Bayesian Networks and Probabilistic Inference in Expert Systems》（Judea Pearl）：贝叶斯网络通常以 DAG 表示变量间的条件依赖关系。
• 《Graph Theory》（Reinhard Diestel）：图论体系化介绍有向图、无环性等基础概念与定理。