有向无环图（DAG）是一种图数据结构，由通过有向边连接的节点组成，其中边具有特定的方向且不形成任何循环。它是一种没有任何有向环的有向图。

DAG 中的每个节点可以有一个或多个入边和一个或多个出边。DAG 中的边表示节点之间的依赖关系，边的方向指示依赖的方向。例如，如果节点 A 有一条指向节点 B 的出边，则意味着节点 A 依赖于节点 B。

概述

有向无环图（DAG）与区块链的不同之处在于它们不使用基于区块的结构。相反，交易被表示为图中的顶点，并链接到之前的交易。节点验证交易并将其添加到 DAG 中，提交交易需要完成一项工作量证明任务。^[1]​

在基于 DAG 的网络中，新交易必须引用之前的交易才能被接受，这类似于区块链中的区块引用之前的区块。引用一笔交易即确认了它，而一笔交易要被完全确认，需要被后续交易引用。^[1]​

由于不存在区块创建，DAG 具有极高的交易速度；又因为没有矿工，所以没有交易费用，这可能具有环境效益。^[2]​

从某种意义上说，DAG 优于区块链，因为它们通过结合区块链、工作量证明和权益证明的概念，以及最长链规则与有向无环图，实现了更高的吞吐量。

历史

DAG 的首次使用时间不详，但这一概念非常实用，可以追溯到人类存在的黎明时期。

莱昂哈德·欧拉（Leonhard Euler）于 1736 年发表的《柯尼斯堡七桥问题》（Seven Bridges of Königsberg）被认为是第一篇涵盖图论的论文。柯尼斯堡七桥问题是数学史上一个著名的问题。挑战在于找到一条路线，穿过柯尼斯堡（现俄罗斯加里宁格勒）的七座桥，每座桥恰好经过一次。在将城市地图简化为图后，欧拉引入了关于边数、顶点数和面数的公式。

从此，图论发展成为一门研究对象之间关系的学科，由数学结构描绘。图有许多不同的类型，都有特定的定义，而 DAG 就是其中之一。^[3]​

使用案例

家族树

DAG 的一个原始使用案例是创建家族树。有趣的是，图论中对“树”的定义并不包括大多数家族树。这是因为在追溯得足够远的家族树中，远亲在某些点上会交配，从而在家族的父系和母系双方都有共同的祖先。这意味着，家族树可以被视为一个 DAG——其中每个节点是一个人，每个父代与后代的关系被绘制为指向后代的箭头。这形成了如下图所示的图，它是有向的（箭头）且无环的（没有人可以是自己的父母）。

古罗马的老普林尼（Pliny the Elder）曾记录过将家族树描绘为 DAG 的做法，他描述了装饰在罗马贵族房屋墙壁上的图表。在此之前，DAG 可能没有被记录下来，但在解释家族史时经常被描述。^[3]​

任务调度

DAG 的另一个历史使用案例是任务调度，动物和人类天生就会使用 DAG 来确定完成任务的顺序。有些任务在其他任务完成之前无法开始，而其他任务可以随时开始——这本身就是一个 DAG。

在上述 DAG 中，T1 可能是决定猎取哪种动物作为晚餐，任务 2 是猎取该动物，而可以同时进行的任务 3 是收集木柴。任务 4 是生火。任务 5（烹饪动物）既需要火在燃烧，也需要动物被猎获，而任务 6 是吃晚餐，这需要动物先被煮熟。类似（但更复杂）的 DAG 曾被用于任何大型任务，如建造金字塔、设计罗马、策划战争期间的攻击等。^[3]​

计算机科学

DAG 的其他使用案例更为现代，有多种与计算机科学相关的用途。数据处理网络、版本历史和一些数据压缩算法都利用了 DAG。但需要注意的重要一点是，DAG 并不是什么新发现，而是一种古老的问题解决机制。DAG 与区块链的融合是分布式账本可扩展性的一次巨大飞跃。^[3]​