1.有向无环图的定义

有向无环图:若一个有向图中不存在环，则称为有向无环图。
简称DAG图(Directed Acyclic Graph)

顶点中不可能出现重复的操作数。

2.有向无环图的应用

1.描述算数表达式

用有向无环图描述算术表达式。

解题步骤：

1. 把各个操作数不重复地排成一排。
2. 标出各个运算符的生效顺序（先后顺序有点出入无所谓)
3. 按顺序加入运算符，注意“分层”（同级的运算为同一层）
4. Step 4:从底向上逐层检查同层的运算符是否可以合体：如果同一层的左右子树一致，则合并为一个子树。

使用有向无环图存储一个表达式，图的最终形态是不唯一的。

案例：

2.拓扑排序