CodeBrick 博客

Appearance

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

核心思想 ​

有向无环图（DAG, Directed Acyclic Graph）是不含有向环路的有向图。它是表示含有公共子表达式的代数表达式的有效工具。

用二叉树表示表达式时，重复出现的子表达式要存储多份。用 DAG 表示时，公共子表达式只需存储一次，通过多个父结点的边共享，从而节省存储空间。

二叉树 vs DAG 表示 ​

以表达式 ((a+b)*(b*(a+b))) 为例：

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

         *
        / \
       +   *
      / \ / \
     a  b b   +
             / \
            a   b

共 9 个结点。

DAG 表示——子表达式 (a+b) 只存一份，被两个父结点共享：

         *
        / \
       +   *
      / \ / ↖
     a   b    （指向左边的 + 结点）

共 5 个结点。操作数 a、b 各出现一次，+ 结点被 *（根）和右侧 * 共享。

构造方法 ​

从表达式的二叉树出发，自底向上合并重复结点：

  1. 检查所有叶子结点，相同操作数的叶子只保留一个
  2. 检查所有内部结点，若两个结点的运算符相同且左右子结点都相同（指向同一结点），则合并为一个
  3. 重复步骤 2，直到没有可合并的结点

关键性质：在 DAG 表示中，不会出现重复的操作数顶点。

真题示例 ​

2019 统考真题：用有向无环图描述表达式 (x+y)((x+y)/x)，需要的顶点个数至少是多少？

分析：

  • 操作数：x, y — 各 1 个结点，共 2 个
  • 子表达式 (x+y) 出现两次，只需 1 个 + 结点
  • / 结点：左子为 + 结点，右子为 x 结点
  • * 结点（根）：左子为 + 结点，右子为 / 结点
      *
     / \
    +   /
   / \ / \
  x   y   x（指向同一个 x 结点）

共需 5 个顶点：x, y, +, /, *。

与其他知识点的联系 ​

DAG 不仅用于表达式优化，在图论中还有两个重要应用：

概念定义与 DAG 的关系
AOV 网顶点表示活动，边表示先后关系DAG 的一种，用于拓扑排序
AOE 网边表示活动（带权），顶点表示事件DAG 的一种，用于关键路径

考研高频考点 ​

  • ⭐ 给定表达式，画出对应的 DAG 并计算最少顶点数（2019 真题原题）
  • ⭐ DAG 与二叉树表示表达式的区别：DAG 共享公共子表达式（选择题）
  • DAG 的定义：有向无环图（概念辨析）
  • DAG 的性质：不存在重复的操作数顶点

易错：计算 DAG 最少顶点数时，不仅要合并相同的操作数，还要合并运算符相同且操作数完全相同的内部结点。比如表达式中出现了两个 a*b，对应的 * 结点也只需一个。

易错：DAG 描述表达式是图论的应用，不要和"二叉树表示表达式"（栈与队列章节）搞混。前者的重点是共享子结构减少空间，后者的重点是用栈计算表达式的值。

相关知识 ​

相关文章