【数据结构】图论实战：DAG空间压缩术——42%存储优化实战解析

导读

大家好，很高兴又和大家见面啦！！！

今天我们将延续图的应用探索，在前两期学习的最小生成树和最短路径基础上，展开图的第三个重要应用方向——**有向无环图（DAG）**。

在前期内容中，我们深入探讨了图的两种经典应用：

• 最小生成树（MST）
  • 解决"全节点连通的最低成本"问题
  • 经典应用：网络布线、电力输送
  • 核心算法：
    • Prim算法：从任意节点开始，贪心添加连接树与非树节点的最小边
    • Kruskal算法：按权重升序选边，用并查集避免成环
• 最短路径
  • 解决"节点间最优路径规划"问题
  • 核心算法：
    • BFS算法：在无权图中实现O(V+E)时间复杂度的单源最短路径
    • Dijkstra算法：非负权重图中的最优单源路径
    • Bellman-Ford算法：支持负权重边并检测负环

🔍 BFS的特殊价值：当边权为1时，其第一次访问路径即最短跳数路径，是理解拓扑排序等高级算法的基础。

今天我们将把目光转向图的另一个精妙应用。当问题涉及执行顺序约束（如任务依赖关系）或计算结构复用（如嵌套表达式）时，DAG凭借其有向无环的特性成为理想解决方案。

💡 为何DAG是自然延伸

• 最小生成树 → 物理连接问题
• 最短路径 → 路径规划问题
• DAG → 依赖关系管理问题

下面我们将通过具体案例，展示DAG如何将表达式存储空间缩减42%，马上开始今天的核心内容！

一、有向无环图描述表达式

有向无环图：一个有向图中不存在环，则称为有向无环图，简称DAG（​​D​​irected ​​A​​cyclic ​​G​​raph） 图。

有向无环图是描述含有公共子式的表达式的有效工具，例如表达式：

在这个表达式中，我们如果将运算符作为根结点，两个操作数作为根结点的左右子树，那么我们就可以通过一棵二叉树来表达上式：

graph TB
A[+]
B[*]
C[*]
D[+]
E[+]
F[+]
G[*]
H[*]
I[+]
J[*]
b1[b]
b2[b]
c1[c]
c2[c]
c3[c]
d1[d]
d2[d]
d3[d]
e1[e]
e2[e]
A---->a
A---->b1
D---->c1
D---->d1
C---->b2
C---->D
B---->A
B---->C
F---->c2
F---->d2
G---->F
G---->e1
E---->B
E---->G
I---->c3
I---->d3
J---->I
J---->e2
H---->E
H---->J

在这么一棵二叉树中，我们不难发现，虽然表达式中只有3种标点符号和5个字母，但是我们却花费了大量的空间将每一个标点符号和每一个字母都记录了下来。

那有没有一种方法能够很大程度上的节省空间呢？

这个就是我们前面提到的有向无环图的功能了，在有向无环图中，我们可以通过把相同的部分进行共享，以此来缩减存储空间的开销。

为了更好的说明有向无环图，下面我们就来一步一步的合并上图中的相同子式；

1.1 过程演示

这里我们从二叉树的最底层开始，按照从左到右的顺序进行合并。该二叉树共有6层，因此我们先从第6层开始：

• 第六层：二叉树的最底层只有两个元素：c和d，显然这是无法进行合并的，因此，这里的元素c和d保留

graph TB
c
d

• 第五层：
  • 在第五层中，我们可以看到，存在两个b，因此这里可以进行合并；
  • 在第五层中同样也存在元素c和d，但是第六层的c、d的父结点是+，但是第五层的我们目前还不清楚，所有这里先保留：

graph TB
a 
b 
+ 
c2[c] 
d2[d]
+---->c1[c]
+---->d1[d]

• 第四层：
  • 在这里层中，我们看到存在两个+，同时又出现了c和d，这一层的c和d我们目前需要保留；
  • 接下来我们来看这一层的两个+，第一个+的左右子树是元素a和b，第二个+的左右子树是元素c和d，这与第五层中的+的左右子树相同，因此这里的+与第五层的+进行合并

graph TB
+1[+]
+2[+]
+1---->a
+1---->b
*---->b
*---->+2
+2---->c
+2---->d
e
c2[c]
d2[d]

• 第三层
  • 第三层中有4个元素：*/*/+/e
  • 第一个*的左右子树分别是第四层的+和*，第二个*的左右子树分别是第四层的+和e，因此这两个*不能合并，需要保留；
  • 这一层的+的左右子树是c和d，与第四层的第二个+和第五层的+相同，因此这里的+可以与第五层的+进行合并；

graph TB
*1[*]---->+1[+]
*1---->*3[*]
+1---->a
+1---->b
*3---->b
*3---->+2[+]
+2---->c
+2---->d
*2[*]---->+2
*2---->e1[e]
e2[e]

• 第二层：
  • 第二层只有两个元素：+/*
  • 这一层的+的左右子树是第三层的两个*，因此需要保留
  • 这一层的*的左右子树是第三层的+和e，这与第三层的第二个*的左右子树相同，因此可以合并

graph TB
+1[+]---->*1[*]
+1[+]---->*2[*]
*1---->+2[+]
*1---->*3[*]
+2---->a
+2---->b
*3---->b
*3---->+3[+]
+3---->c
+3---->d
*2---->+3
*2---->e

• 第一层
  • 第一层只有一个元素*
  • 其左右子树分别是第二层的+和*，这里需要保留

graph TB
*0[*]---->+1
*0---->*2
+1[+]---->*1[*]
+1[+]---->*2[*]
*1---->+2[+]
*1---->*3[*]
+2---->a
+2---->b
*3---->b
*3---->+3[+]
+3---->c
+3---->d
*2---->+3
*2---->e

可以看到，经过合并后，我们目前只使用了12个结点就完成了该表达式的描述，相比于之前的二叉树的21个结点，我们就节省了9个结点的存储空间；

1.2 DAG图的读取

当我们要读取一个DAG图时，也很简单，我们同样只需要从最底层开始即可，如下所示：

• 首先我们读取到的是元素c和d，这两个操作数的操作符是+，因此我们记录下第一部分：c+d
• 接下来我们读取到的是元素a和b，这两个操作数的操作符是+，因此我们记录下第二部分：a+b
• 第一部分的c+d作为操作数时，它的操作符是*，而该操作符的另一个操作数指向的时元素b，因此第三部分应该是由b和c+d作为操作符*的左右操作数组成，我们记录下第三部分：b*(c+d)
• 第二部分的a+b作为操作数时，它的操作符是*，而该操作符的另一个操作数指向的是第三部分b*(c+d)，因此这一部分是有左右操作数a+b、b*(c+d)与其操作符*共同组成，我们记录下第四部分：(a+b)(b(c+d))
• 第四部分的(a+b)(b(c+d))作为操作数时，其操作符是+，而该操作符的另一个操作数指向的是*，下面我们继续查找*的左右操作数； *指向的左操作数是操作符+，右操作数是e，其左操作数的操作符+指向的事操作数c和d，因此该部分我们记为(c+d)*e 第四部分的操作数与*这部分的操作数与操作符+共同组成了第五部分，我们记录下第五部分：(a+b)(b(c+d))+((c+d)*e)
• 第五部分的(a+b)(b(c+d))+((c+d)*e)作为操作数时，其操作符为*，该操作符指向的另一个操作数为*，这里我们将操作符*记为*1，操作数的*记为*2，下面我们继续查找*2的左右操作数 *2指向的左右操作数分别是+和e，而操作符+指向的左右操作数为c和d，因此该部分为：(c+d)*e 第五部分与*2部分作为操作数与操作符*1共同组成了第六部分，因此我们记录下第六部分：((a+b)(b(c+d))+((c+d)e))((c+d)*e)
• 第六部分已经无法作为操作数继续向上查找，因此第六部分就为该DAG图所描述的表达式，我们将该表达式中多余的()删除后就得到了最终的表示式：

结语

通过本文的探讨，我们深入理解了有向无环图（DAG） 的核心价值： 空间高效性：将表达式 ((a+b)(b(c+d))+(c+d)e)((c+d)*e) 的存储节点从二叉树的21个压缩至DAG的12个，节省了42% 的存储空间

• 依赖可视化：通过分层合并与结点共享（如复用 (c+d) 子式），直观呈现计算逻辑中的复用关系
• 应用普适性：为编译器优化、任务调度等需要管理依赖关系的场景提供了天然解决方案

💡 核心洞察：DAG通过有向性建立执行顺序，通过无环性保障逻辑可行性，这正是解决复杂依赖问题的关键！

DAG的精妙远不止于此！ 在下一篇内容中，我们将解锁DAG的杀手级应用——

🔥 拓扑排序（Topological Sorting）

• 当需要确定任务执行顺序（如课程学习计划、项目依赖管理）时
• 当依赖关系复杂但必须保证无死锁执行时
• 当Git提交历史需要线性化输出时

我们将揭秘： ✅ 如何将DAG转化为线性序列 ✅ Kahn算法与DFS实现的双重解析 ✅ 动态任务调度系统的底层逻辑 剧透亮点：拓扑排序本质上是对DAG的BFS/DFS高阶应用，这与我们在最短路径中讨论的BFS算法形成了奇妙的知识闭环！