7.5 有向无环图

01有向无环图

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

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

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

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

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

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

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。