拓扑排序依赖图中的边方向？

Question

Wikipedia以一种非常直观的方式(IMO)解释了依赖关系图，引用了当a依赖于B时，a=>B会产生边。换句话说，我们可以通过查看其邻接列表中可用的邻居立即找到任何给定节点的直接依赖关系（如果有的话）。

这似乎是实现依赖的一个明智的方法；它允许我们基本上像执行深度优先遍历（图中每个节点的DFS）一样容易地执行拓扑排序。如果节点表示“任务”，那么只有当任务的所有传递依赖项都已执行/访问时，我们才能执行/访问任务。叶节点是第一个被访问的节点，依此类推。

关于拓扑排序的维基百科页面将定义解释为：

在计算机科学中，有向图的拓扑排序或拓扑排序是它的顶点的线性排序，因此对于从顶点u到顶点v的每个有向边uv，u在排序中位于v之前。

这与我期望的“依赖关系图”相反。我们刚刚解释了，如果a依赖于B，则存在一个有向边a=>B，并且我们必须在a之前访问/执行B。但是，根据上面解释的图，由于我们在V之前执行/visit任务U，因此，V依赖于U。因此，如果我没有弄错的话，Wiki的topo排序页面所期望的输入图似乎是一个边反转的“依赖图”。页面上的算法证实了这一点；例如，他们的DFS方法将从节点n开始，递归到依赖于n（而不是n的依赖项）的节点，然后将n前置到某个列表的头部，以便它比其依赖项出现得更早。结果与我解释的DFT相同，明确地说，我并不是说任何一页都是错的，它只是演示了几种做某事的方法。

虽然Wiki有依赖关系图的这种定义，但它似乎在拓扑排序页面上使用了它的相反的定义，通过反向依赖关系的递归，并基本上反向输出列表，这确实让人感到奇怪。

我唯一的问题是：是否有一些明显的原因我忽略了，拓扑排序页面上的预期图基本上与“依赖图”DFN相反？我们从n遍历n的依赖项，并通过记录到堆栈之类的东西来有效地反向输出，这感觉很不直观。

更一般地说，拓扑排序页面所期望的图似乎并不是一个好的依赖图。如果我们认为这个图是规范的“依赖关系图”，那么为了找到n的依赖关系，我们必须遍历整个图，询问“这个节点指向n吗？”，这似乎很奇怪。

Answer 1

拓扑排序产生与偏序一致的总序。

偏序和DAG是一样的。

我们经常根据依赖图对项目进行拓扑排序······

但我们通常使用的偏序是“必先”图，而不是“依赖”图。这是同一张图，但边反转了。

我认为你错过了两件事：

1）图是数据结构的解释。数据结构不是图。在大多数实际情况下，图算法应用于不是字面上或显式地表示图本身的数据结构。在这种情况下，如果有一个从a到B的指针，我们排序的DAG就有一个从B到a的边缘。

2）在DAG中颠倒边仅仅意味着颠倒最终的拓扑排序，或者从另一端开始。这并不重要，所以在口语中，很自然地谈论依赖图的拓扑排序，而不是边颠倒的依赖图的拓扑排序。降序排序仍然是排序，逆拓扑排序仍然是拓扑排序。