Dom*_*ino 1 algorithm graph depth-first-search topological-sort
维基百科以非常直观的方式（IMO）解释了依赖图，引用了一条边来自于a => b何时a依赖于b。换句话说，我们可以通过查看其邻接列表中的邻居立即找到任何给定节点的直接依赖关系（如果有）。
这似乎是实现依赖关系的明智方式；它使我们能够像执行深度优先遍历（图中每个节点的 DFS）一样轻松地执行拓扑排序。如果节点代表“任务”，那么只有当任务的所有传递依赖项都已执行/访问时，我们才能执行/访问任务。叶节点是最先被访问的，依此类推。
拓扑排序的维基百科页面将定义解释为：
在计算机科学中，有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中位于 v 之前。
这与我所期望的“依赖图”相反。我们刚刚解释了如果a依赖b，则存在有向边，并且我们必须在之前a => b访问/执行。然而，根据上面解释的图，由于我们在 之前执行/访问任务，所以理所当然地取决于。因此，如果我没有记错的话，Wiki 的拓扑排序页面期望的输入图似乎是一个边缘反转的“依赖图”。页面上的算法证实了这一点；例如，他们的 DFS 方法将从一个节点开始，递归到依赖于（而不是依赖项）的节点，然后添加到某个列表的头部，以便它比其依赖项出现得更早。结果与我解释的 DFT 相同，需要明确的是，我并不是说任一页面上的任何内容都是错误的，它只是演示了执行某些操作的几种方法。b auvvunnn n
尽管 Wiki 有依赖关系图的定义，但似乎在拓扑排序页面上使用其逆，通过反向依赖关系递归，并本质上反转输出列表，这确实感觉很奇怪。
我唯一的问题是：是否有一些我遗漏的明显原因，即拓扑排序页面上的预期图形基本上与“依赖图”dfn 相反？n我们从to的依赖项遍历n，并通过记录到堆栈之类的东西来有效地反转输出，这感觉很不直观。
更一般地说，拓扑排序页面似乎期望的图无论如何似乎都不是一个好的依赖图。如果我们认为这个图是规范的“依赖图”，那么为了找到n的依赖关系，我们必须迭代整个图询问“这个节点是否指向 n？”，这看起来很奇怪。
拓扑排序产生与部分排序一致的全排序。
部分排序与 DAG 相同。
我们经常根据依赖图对项目进行拓扑排序......
但我们通常使用的偏序是“必须先于”图，而不是“取决于”图。这是同一张图，但边缘相反。
我认为你缺少的两件事是：
1）图是对数据结构的解释。数据结构不是图。在大多数现实生活中，图算法应用于不字面或明确表示图本身的数据结构。在本例中，有一个来自ato 的指针b，我们正在排序的 DAG 具有一条从bto 的边a。
2）反转DAG中的边只是意味着反转最终的拓扑顺序，或者从另一端开始。这并不重要，所以在口语中，很自然地谈论对依赖图进行拓扑排序，而不是对边反转依赖图进行拓扑排序。降序排序仍然是排序，逆拓扑排序仍然是拓扑排序。