# Directed Acyclic Graph (DAG)

> 有向无环图（DAG）是一种具有有向边且无回路的图，代表了每个节点仅指向一个方向的依赖关系。

- Canonical URL: https://iq.wiki/zh/wiki/directed-acyclic-graph-dag
- Categories: Glossary
- Created: 2023-04-28T23:56:57.443Z
- Last updated: 2026-06-02T15:06:14.336Z
- Source: IQ.wiki — the world's largest blockchain and crypto encyclopedia (https://iq.wiki)

---

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

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

[YOUTUBE@VID](1Yh5S-S6wsI)

## 概述

有向无环图（DAG）与[区块链](https://iq.wiki/wiki/blockchain)的不同之处在于它们不使用基于区块的结构。相反，交易被表示为图中的顶点，并链接到之前的交易。节点验证交易并将其添加到 DAG 中，提交交易需要完成一项[工作量证明](https://iq.wiki/wiki/proof-of-work-pow)任务。[\[1\]](#cite-id-r8jhmqlyjh8)​

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

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

从某种意义上说，DAG 优于区块链，因为它们通过结合区块链、[工作量证明](https://iq.wiki/wiki/proof-of-work-pow)和[权益证明](https://iq.wiki/wiki/proof-of-stake)的概念，以及最长链规则与有向无环图，实现了更高的吞吐量。

### 历史

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

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

![](https://ipfs.everipedia.org/ipfs/QmPVHMd492MVV6iuCjYZENanJ9uRoaCtW11HddBuhzdabX)

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

## 使用案例

### 家族树

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

![](https://ipfs.everipedia.org/ipfs/Qmc78jejbpBBxcNtcTi74g9D6pH4weVoAXxnYXjzhH2oM5)

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

### 任务调度

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

![](https://ipfs.everipedia.org/ipfs/QmaRAMVYdMXgUQhxRUakaHyrYyBHisKbPpP9VGYFfHm5QR)

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

### 计算机科学

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