7.5 有向无环图

01有向无环图

1、一个无环的有向图称做有向无环图（directed acycline graph），简称DAG图，DAG图是一类较有向树更一般的特殊有向图。

2、有向无环图是描述含有公共子式的表达式的有效工具。

3、若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。

4、检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边，则必定存在环，而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。

5、有向无环图也是描述一项工程或系统的进行过程的有效工具。

6、几乎所有的工程都可分为若干个称做活动的子工程，而这些子工程之间，通常受着一定条件的约束。

7、拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序。

8、路径长度最长的路径叫做关键路径。

C语言 | 用%f控制符输出6位小数​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338750312