DAG 和顶黑
DAG and Top Sort
"Arranging the vertices of a DAG according to increasing pre-number results in a topological sort." 显然不是正确的陈述，但我不明白为什么不是。如果图是有向的并且没有环，那么我们访问顶点的顺序不应该是我们拓扑排序的正确顺序吗？
通过增加前置编号排列并不能保证有效的拓扑排序。考虑这张图：
A
↓
B → C → D
该图的两个有效拓扑顺序是：
A, B, C, D
B, A, C, D
如果您要访问以 C 开头的节点，一种可能的预编号顺序是：
C, D, A, B
这不是有效的拓扑顺序。一个更简单的例子是这张图：
B → A
显然有一个有效的拓扑顺序，但如果我们首先访问 A 并按前序号排序，结果顺序将是倒序的。
"Arranging the vertices of a DAG according to increasing pre-number results in a topological sort." 显然不是正确的陈述，但我不明白为什么不是。如果图是有向的并且没有环，那么我们访问顶点的顺序不应该是我们拓扑排序的正确顺序吗？
通过增加前置编号排列并不能保证有效的拓扑排序。考虑这张图：
A
↓
B → C → D
该图的两个有效拓扑顺序是：
A, B, C, D
B, A, C, D
如果您要访问以 C 开头的节点，一种可能的预编号顺序是：
C, D, A, B
这不是有效的拓扑顺序。一个更简单的例子是这张图：
B → A
显然有一个有效的拓扑顺序，但如果我们首先访问 A 并按前序号排序，结果顺序将是倒序的。