有向无环图（DAG）描述表达式

2026 大纲 五（四）图的基本应用 3. 拓扑排序（有向无环图的应用之一；DAG 的定义与 AOV 网见《拓扑排序》）。

二叉树存表达式，重复的部分要存好几份

表达式 $(x + y) \times ((x + y) / x)$ ，用二叉树（语法树）画出来是什么样？

根是 $\times$ ，左子树是一个 $+$ 挂着 $x$ 和 $y$ ，右子树是一个 $/$ ，它的左边又是一个 $+$ 挂着 $x$ 和 $y$ 、右边是 $x$ 。数一数结点： $x$ 出现 3 次、 $y$ 出现 2 次、 $+$ 两个、 $/$ 一个、 $\times$ 一个，一共 9 个。

问题出在二叉树的每个结点只能有一个双亲。子表达式 $(x + y)$ 在表达式里出现了两次，就必须存两份完整的子树——哪怕这两份一模一样。

DAG 解除了这个限制：一个顶点可以有多个双亲。于是重复的子表达式只存一份，由多条边共享。同一个表达式画成 DAG， $x$ 一个顶点、 $y$ 一个顶点、 $(x + y)$ 一个顶点（被两条边指着）、 $/$ 一个、 $\times$ 一个，只要 5 个。

代价是它不再是树。但表达式的依赖方向永远是"父表达式 → 子表达式"，而子表达式严格更短，绕不回来，所以这个结构天然无环——DAG 这个名字里的 A（Acyclic）是免费得来的。

数顶点：列子表达式，不要画图凑

这是本篇唯一真正要会做的事，而且有一条不用画图的捷径：

🔴 DAG 的最少顶点数 = 该表达式中互不相同的子表达式（含单个操作数）的个数。

拿 $(x + y) \times ((x + y) / x)$ 逐个列：

序	子表达式	类型
1	$x$	操作数
2	$y$	操作数
3	$(x + y)$	运算符 $+$
4	$((x + y) / x)$	运算符 $/$
5	$(x + y) \times ((x + y) / x)$	运算符 $\times$ （根）

5 个。列表比画图快，也不容易漏。

边数要分开数，别用顶点数去凑：二元运算符顶点的出度恰为 2、操作数顶点出度为 0，所以

边数 = 2 \times 二元运算符顶点数

（一元运算符如取负出度为 1，单独算。）上例三个二元运算符，边数 $= 6$ 。

合并的三条判据，缺一不可

从语法树出发自底向上合并：

合并叶子：所有表示同一个操作数的叶子，只保留一个。
合并内部结点：两个结点要满足运算符相同 + 左孩子指向同一顶点 + 右孩子指向同一顶点，三条全中才能合并。
重复第 2 步直到没有可合并的为止。

为什么必须自底向上？ 因为第 2 条判据里"左右孩子指向同一顶点"这个条件，只有在孩子已经合并完之后才判得准。自顶向下会漏掉本可合并的机会。

"至少需要多少个顶点"这个问法没有歧义：合并规则是确定性的——满足判据的必须合并、不满足的不能合并，所以完全合并后的 DAG 唯一，顶点数也唯一。

两个不能越界的地方

第一，DAG 不做代数化简。 它消除的是结构上完全相同的重复，不是数学上等价的东西：

$a \times b$ 与 $b \times a$ 不能合并。乘法虽可交换，但这两个结点的左孩子不同、右孩子也不同，判据第 2、3 条都不满足。
$a - b$ 与 $b - a$ 更不能——它们的值本来就不同。同理 $X / Y$ 与 $Y / X$ 是两回事。画图时左右孩子的位置是有意义的。

第二，代数等价的两个表达式，DAG 顶点数可以不同。 $a \times b + a \times c$ 的不同子表达式是 $a, b, c, (a \times b), (a \times c)$ 与根，共 6 个； $a \times (b + c)$ 是 $a, b, c, (b + c)$ 与根，共 5 个。DAG 不会自动提公因式。

结构性质与自检

性质	理由
一定无环	边的方向永远是"父表达式 → 子表达式"，子表达式严格更短
有且仅有一个入度为 0 的顶点	就是整个表达式对应的根
操作数顶点出度为 0	它们是叶子
二元运算符顶点出度恰为 2	左右各一条边
入度可以大于 1	这正是"共享"的表现，也是它区别于二叉树的唯一地方
没有重复的操作数顶点	合并规则第 1 条的直接结果

画完图的自检清单：入度为 0 的顶点只有一个吗？每个二元运算符顶点的出度是 2 吗？同名操作数是不是只画了一个？三条都对，图基本不会错。

二叉树与 DAG 的完整对照走查（第一次学、想看清"省下的是什么"就展开）

以表达式 $((a + b) \times (b \times (a + b)))$ 为例。

二叉树表示——子表达式 $(a + b)$ 被存了两份：

逐个数：根 *、左子树的 +、a、b，右子树的 *、b、+、a、b，共 9 个结点。

DAG 表示—— $(a + b)$ 只存一份、被两个父结点共享， $a$ 、 $b$ 也各只存一份：

共 5 个顶点： $a$ 、 $b$ 、 $+$ 、 $\times$ （内层）、 $\times$ （根）。从 9 降到 5。边数 $= 3 \times 2 = 6$ 条。

再看一张含不可交换运算符的图： $(a - b) / ((a - b) \times c) + (c - a)$ 。不同的子表达式是 $a$ 、 $b$ 、 $c$ 、 $(a - b)$ 、 $((a - b) \times c)$ 、 $(a - b) / ((a - b) \times c)$ 、 $(c - a)$ 与根，共 8 个顶点；二元运算符顶点 5 个，边数 $= 5 \times 2 = 10$ 。

图上两个 $-$ 顶点没有合并：运算符相同，但一个的孩子是 $(a, b)$ 、另一个是 $(c, a)$ ，左右孩子都不同。含不可交换运算符时最容易犯的错，就是"看到两个 $-$ 就想合并"。 而三个 $a$ 合并成了一个——叶子只看操作数名，出现在哪里都一样。

存储结构与逆向还原表达式（写代码或被问到"怎么存"时展开）

表达式 DAG 的每个顶点最多有两个后继（左、右操作数），所以可以直接沿用二叉链表式的结点结构，只是允许多个结点指向同一个孩子：

typedef struct DagNode {
    char  data;                        // 操作数名，或运算符 '+' '-' '*' '/'
    int   isOperator;                  // 1 表示运算符结点，0 表示操作数结点
    struct DagNode *lchild, *rchild;   // 操作数结点这两个域为 NULL
} DagNode;

与二叉树的唯一差别：二叉树里"两个结点的 lchild 指向同一个地址"是错误（会造成重复释放、修改互相污染），在 DAG 里这恰恰是共享的实现方式。

也正因为存在共享，释放整张 DAG 不能用二叉树那套后序递归 free——同一个结点会被 free 多次；要么给每个结点加引用计数，要么另开一张"已释放"表。

若用邻接表存，就是一张普通的有向图邻接表，每个运算符顶点的边链表上恰有两个结点（次序不能乱，第一个是左操作数）。

由 DAG 反向写出表达式：从入度为 0 的根出发做后序遍历，每到一个运算符结点就写成 (左子表达式运算符右子表达式)。⚠️ 共享结点会被"读到"多次，但只存一次——一个入度为 2 的顶点，在还原出的表达式里就要出现两次，这是逆向最容易漏抄的地方。

与其他 DAG 应用的关系

DAG 在本章一共承担三类应用，共同点是"有向 + 无环"，但关心的东西完全不同：

应用	顶点表示	边表示	关心什么	在哪一篇
表达式 DAG	子表达式	依赖（父指向子）	顶点数最少（共享子结构省空间）	本篇
AOV 网	活动	先后关系	排出一个合法顺序（拓扑排序）	拓扑排序
AOE 网	事件	活动（带权 = 时长）	工期与关键活动（关键路径）	关键路径

表达式 DAG 也可以做拓扑排序——得到的正是一个合法的求值顺序：按逆拓扑序（先算被依赖的子表达式）逐个求值，每个子表达式只算一次。这就是编译器里"公共子表达式消除"这一优化的雏形：DAG 省的不只是空间，还有重复计算的时间。

考点速记

三条结论：

DAG 的最少顶点数 = 互不相同的子表达式（含单个操作数）的个数——按这条列表数，不用画图凑。
合并判据：运算符相同 + 左孩子同一顶点 + 右孩子同一顶点，三条缺一不可，且只能自底向上做。
边数 $= 2 \times$ 二元运算符顶点数；唯一入度为 0 的顶点是根；操作数顶点不重复。

这一节在真题里被考过的形式：目前只出现过一种问法，而且落在同一道选择题里——

"用有向无环图描述表达式 $E$ ，需要的顶点个数至少是多少"：给一个含公共子表达式的表达式（如 $(x + y) \times ((x + y) / x)$ ），四个选项从"完全不合并"（等于语法树的结点数）一路递减到正确答案。四个干扰项恰好对应四种合并力度：完全不合并、只合并变量不合并 $(x + y)$ 、只合并了一部分变量、以及正确的完全合并。做法就是列出全部互不相同的子表达式再数一遍。

注：这道题在题库里挂在「图的基本概念」这个考点下，所以本篇下方没有单独的「真题练习」区块——不是漏挂。要练可以到那一篇的真题列表里找"用有向无环图描述表达式"那道。

易错：DAG 不做代数化简。 $a \times b$ 与 $b \times a$ 不能合并（左右孩子不同）， $a \times b + a \times c$ 与 $a \times (b + c)$ 的顶点数也不相等（6 对 5）。合并的判据是结构相同，不是值相等。

易错：公共子表达式本身也要合并，不只是变量。 只把重复的 $x$ 、 $y$ 叶子合并、却把两个 $(x + y)$ 各算一个加号顶点，是这类题被摆在选项里的头号错法。

易错：边数不能从顶点数推。 边数 $= 2 \times$ 二元运算符顶点数，操作数顶点一条出边都没有，两者分开数。

教材出处

严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p176，§6.6.3 之 1： "一个无环的有向图称作有向无环图 (Directed Acycline Graph)，简称 DAG 图。有向无环图是描述一项工程或系统的进行过程的有效工具。" ——本篇的 DAG 定义以此为准；该书这一节随后展开的是 AOV 网与拓扑排序，表达式 DAG 属同一类"有向无环图的应用"。

有向无环图（DAG）描述表达式

二叉树存表达式，重复的部分要存好几份

数顶点：列子表达式，不要画图凑

合并的三条判据，缺一不可

两个不能越界的地方

结构性质与自检

与其他 DAG 应用的关系

考点速记

相关知识

相关文章

有向无环图（DAG）描述表达式 ​

二叉树存表达式，重复的部分要存好几份 ​

数顶点：列子表达式，不要画图凑 ​

合并的三条判据，缺一不可 ​

两个不能越界的地方 ​

结构性质与自检 ​

与其他 DAG 应用的关系 ​

考点速记 ​

相关知识 ​

相关文章

有向无环图（DAG）描述表达式

二叉树存表达式，重复的部分要存好几份

数顶点：列子表达式，不要画图凑

合并的三条判据，缺一不可

两个不能越界的地方

结构性质与自检

与其他 DAG 应用的关系

考点速记

相关知识