《CI论》· 有向无环图

Vector_Mingfan · 2021-07-15 15:22:55 · 个人记录

总目录

Ⅰ. 定义

Ⅱ. 性质

Ⅲ. 判定

Ⅳ. 更新日志

Ⅰ. 定义

有向无环图：边有向，且此图无环，在OIer口中也称之为 DAG ， DAG 也和 拓扑排序 息息相关（见图）

反例：（标准的有向有环图）

Ⅱ. 性质

• 能拓扑排序 （链接代填） 的图，一定是有向无环图。

• 有向无环图 一定能拓扑排序。

形象表达两者（ topsort 、 DAG ）的关系图：

Ⅲ. 判定

法一. 检验此图是否可以拓扑排序即可。

法二. 利用 DFS ，搜索此图是否存在返祖边，如果有那就是环，则不是有向无环图。