什么是有向无环图 (DAG)？

有向无环图 (DAG) 是一种图形类型，其中节点通过不形成任何循环的单向连接进行连接。DAG 用于说明依赖关系和因果关系。

与所有图表一样，DAG 有助于可视化代表数据、任务或事件的节点之间的关系。但是，DAG 在描述事件按特定顺序发生的系统时非常有用，例如为实现某个目标而必须完成的任务计划。

DAG 对于创建因果图也很重要：DAG 可以表示某些节点影响其他节点的系统，但因果影响不会反向产生作用。这种单向关系的一个基本示例可以在家族树中找到，因为 DAG 映射连续几代的父母和子女。

DAG 的应用在计算机科学中很常见，开发人员和工程师将 DAGS 用于数据管道和数据处理、神经网络架构、机器人等领域。

为了更好地理解什么是有向无环图，让我们先对其构成进行分解：

节点：节点又称顶点，表示图形上的实体、对象或变量。它们通常用点或圆圈表示。

边缘：边缘表示实体之间的连接。它们用线条表示。

定向边缘：定向边缘表示只能从一个方向遍历的连接。这些边缘上的箭头指示它们的方向。

有向图：指的是完全由有向边缘组成的图。相反，没有有向边缘的图就是无向图。

碰撞器：碰撞器是有 2 条有向边缘指向它们的节点。

路径：路径是将一个给定节点连接到另一个节点的一系列边缘。完全由定向边缘组成的路径称为定向路径。表示因果关系的有向路径称为因果路径。

树：在计算机科学中，树是一种有向无环图，其中除了起始节点（“根”节点）外，每个节点都只有 1 条指向它的有向边缘。虽然边缘从根节点延伸，但没有边缘指向根节点。

除了了解 DAG 的各个部分之外，认识到它缺少的一个组件也很重要：循环。有向无环图中的“无环”是指这些图中没有循环或闭环。换言之，当从 DAG 中的 1 个节点开始并遍历后续节点和边缘时，则不可能返回到起始节点。

在图论（对图的研究）中，处理有向无环图时通常会应用多个概念或流程。其中包括：

• 拓扑排序
• 传递闭包
• 传递归约

拓扑排序（又称“拓扑序列”），是将DAG 节点按线性排列的方法，确保被指向的节点优先出现，且后继节点绝不先于其前驱节点出现。拓扑排序算法可以生成基于 DAG 的序列。 ¹

在复杂图形中，要识别哪些节点可以通过其他节点的有向路径“可达”，可能会比较困难。在传递闭包中，节点之间的这种间接连接被识别并以图表形式呈现。

例如，如果图中有一个连接节点 A 和节点 B 的有向边缘，还有一个连接节点 B 和节点 C 的有向边缘，则表示 A 和 C 是间接连接的。除了 A 和 B 以及 B 和 C 之间原有的有向边缘之外，传递闭包还会产生一条连接 A 和 C 的全新有向边缘，即这两个节点之间的最短路径。与拓扑排序一样，可以使用算法进行传递闭包计算。

传递归约可以说是传递闭包的反义词。在有向图的上下文中，图形的传递归约具有与原始图形相同的节点数，并且可访问的节点对相同。但是，图形的传递归约中的边缘数量会被减至最小。

例如，设想一个原始图，其中包括连接节点 A 到节点 C 的有向边缘，以及连接节点 A 到节点 B 和节点 B 到节点 C 的有向边缘序列。该图的传递归约将排除 A 和 C 之间的边缘，同时保留更大的变量集：A 和 B 以及 B 和 C 之间的边缘。

换句话说，原图中 A 和 C 之间的最长路径包含在新图中，而只有 1 条边缘的路径被消除。

有向无环图在计算机科学中占有重要地位，它有很多用例：

• 数据处理
• 神经网络
• 机器学习中的因果推理
• 机器人
• 编译器设计
• 区块链

DAG 可帮助数据工程师定义数据结构并实现数据流优化。例如，Apache Airflow 等数据编排平台使用 DAG（在 Python 脚本中定义）来定义数据处理任务并指定其在数据管道和工作流中的执行顺序。

在多个 DAG 相互依赖的情况下，编排工具可以创建依赖关系图来阐明这些关系。²数据可观察性平台可以与数据编排平台结合使用，以识别和解决数据管道问题。

依赖于数据访问的生成式 AI 应用的加速采用，增加了数据管道和 DAG 在现代技术领域的重要性。

神经网络是一种机器学习程序，其决策机制模拟人脑工作原理，通过使用生物神经元协同工作的方式进行观察并得出结论。DAG 用于映射神经网络，在具有多层深度神经网络的可视化中大有帮助。

DAG 可以在“指导”AI 模型通过因果推理识别因果关系的过程中发挥作用。因果推理是一种确定因果效应的范例，通常采用 DAG。例如，DAG 可以帮助检测“混杂因素”，即扭曲或掩盖真正因果关系的变量。通过因果推理增强的 AI 技术正在成为流行病学领域的一种工具，特别是有可能帮助研究人员调查疾病决定因素。³

研究人员提议使用基于 DAG 和大型语言模型的结构规划方法来提高双臂机器人的性能。在所提出的框架中，LLM 会生成一个 DAG，将复杂任务划分为子任务，并通过边缘表示其依赖关系。在该框架中，这些信息可用于确定运动规划和协调机器人的双臂，以执行任务。⁴

DAG 可用于优化编译器的设计，编译器是将编程语言（源代码）转换为计算机指令（机器代码）的程序。例如，DAG 有助于识别可删除的常见子表达式，以提高效率。

研究人员表示，基于 DAG 的区块链表现出比传统区块链更好的性能。基于 DAG 的区块链可以允许并行处理事务，从而提高一定时期内事务的处理速度，并实现更大的灵活性和可扩展性。此类改进可应用于供应链管理和物联网网络的访问控制等领域。^5，6