存在非拓扑序边的无环有向图是否属于DAG的技术咨询

咱们先把核心概念掰清楚，直接给你结论：这个无环有向图仍然是DAG，完全不需要所有边的“排序”符合拓扑序——因为DAG的定义和边的列举顺序毫无关系，拓扑排序也不是DAG的必要条件（反过来，DAG是存在拓扑排序的充分必要条件）。

具体拆解一下：

• DAG的本质定义：DAG的全称是Directed Acyclic Graph，翻译过来就是有向无环图。它的判定标准只有两个：

  1. 是一个有向图（边有明确的方向）；
  2. 图中不存在任何有向环（从任意节点出发，沿着边的方向走，永远回不到起点）。
     只要满足这两点，不管你怎么列举边、不管边的顺序是什么，它都是DAG。你提到的边(2,1)，只要整个图里没有环，那就完全符合DAG的要求。

• 拓扑排序的角色：拓扑排序是DAG的一个性质，而不是定义。准确来说是：所有DAG都至少存在一种拓扑排序，但拓扑排序只是对图中节点的一种线性排列方式——要求对于图中的每一条边(u, v)，在这个排列里u都出现在v的前面。
  你说的“当前的边排序不符合拓扑序”，其实是混淆了“边的列举顺序”和“拓扑排序的节点顺序”。比如边(2,1)对应的拓扑排序里，节点2必须在1前面，但这只是节点的排列要求，和你写边的顺序没关系。哪怕你把这条边放在其他边后面，图的结构还是那个无环有向图，依然是DAG。

举个最简单的例子：假设你的图只有两个节点2和1，一条边(2,1)，这显然是无环的，所以它是DAG。它的拓扑排序就是[2,1]，但不管你把这条边写成什么顺序，都不改变它是DAG的事实。

总结一下：判断是不是DAG，只看有没有有向环；拓扑排序是DAG的一个衍生性质，是节点的一种合法排列，和边的顺序、图的边的列举方式无关。

内容的提问来源于stack exchange，提问作者user6575289