有向无环图
定义¶
边有向，无环。
英文名叫 Directed Acyclic Graph，缩写是 DAG。
性质¶
能拓扑排序的图，一定是有向无环图；
如果有环，那么环上的任意两个节点在任意序列中都不满足条件了。
有向无环图，一定能拓扑排序；
（归纳法）假设节点数不超过 的 有向无环图都能拓扑排序，那么对于节点数等于 的，考虑执行拓扑排序第一步之后的情形即可。
判定¶
如何判定一个图是否是有向无环图呢？
检验它是否可以进行拓扑排序即可。
当然也有另外的方法，可以对图进行一遍DFS，在得到的 DFS 树上看看有没有连向祖先的非树边（返祖边）。如果有的话，那就有环了。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用