下图是DAG吗？
Is the following figure DAG?
我看了很多DAG的定义，都说是无环有向图。还有，据说它是有拓扑序的。
现在下图是有向图，没有环
但是看边的顺序（看边(2,1)），它不是拓扑有序的。
这仍然是 DAG 还是每条边都必须拓扑排序才能使该图成为 DAG？
是的，这是一个 DAG。要检查：您不能从一个节点开始并沿着图中的边再次到达它。事实上，该图是 完整 有向无环图，因为它在 3 个节点的 DAG 中包含最大可能边数。添加任何新边都会将其变成循环有向图。
对于完整的DAG，只有一种拓扑顺序。在你的情况下是 0>2>1。
生成拓扑排序的非正式方法：
- 选择源——传入边为零的源（以防万一
很多，任选一个）。
- 将它从图中移除（当然还有它的出边）。
- 重复直到得到空图。
我看了很多DAG的定义，都说是无环有向图。还有，据说它是有拓扑序的。
现在下图是有向图，没有环
但是看边的顺序（看边(2,1)），它不是拓扑有序的。
这仍然是 DAG 还是每条边都必须拓扑排序才能使该图成为 DAG？
是的，这是一个 DAG。要检查：您不能从一个节点开始并沿着图中的边再次到达它。事实上，该图是 完整 有向无环图，因为它在 3 个节点的 DAG 中包含最大可能边数。添加任何新边都会将其变成循环有向图。
对于完整的DAG，只有一种拓扑顺序。在你的情况下是 0>2>1。
生成拓扑排序的非正式方法：
- 选择源——传入边为零的源（以防万一 很多，任选一个）。
- 将它从图中移除（当然还有它的出边）。
- 重复直到得到空图。