有向图的拓扑排序中有一条边

概念

在图论中，有向图是一种图，其中每条边都是有方向的，从一个顶点（称为起点）指向另一个顶点（称为终点）。在有向图中，拓扑排序是将所有顶点排序的线性算法，使得图中的每条边都从前面的顶点指向后面的顶点。因此，如果一条有向边从顶点 A 指向顶点 B，则 A 必须先于 B 应进行拓扑排序。

误区

然而，在拓扑排序过程中，有些人认为，如果有一个顶点 A 指向 B，那么在排序中必须将 A 放在 B 的前面。其实，这是一个错误观念，因为拓扑排序的目的是将所有的顶点按照它们之间的依赖关系排序，而并不是将它们彼此分开。因此，如果 A 向 B 有一条边，但是 A 又依赖于 B，那么 A 不得不放在 B 的后面。

举例

让我们来看一个具体的例子，如下图所示。这是一个图，其中节点之间的箭头表示节点之间的依赖关系。


如果我们尝试对这个图进行拓扑排序，那么 A 应该排在最前面，因为它没有向其他节点指向任何边。然后是 B 和 C，这是因为它们都依赖于 A。接下来是 D 和 E，因为它们依赖于 B 和 C。最后是 F，因为它依赖于 D 和 E。

但是，如果我们修改一下图，将 C 的箭头指向 B，得到以下图：


在这种情况下，B 依赖于 C，但 C 又向 B 指向一条边。此时，以 A 为起点的路径可以到达 B，但是从 B 到达 A 的路径被中断了。这种情况称为“有环图”，也即图中出现了环路，这导致无法对图进行拓扑排序。

如果我们强制对这个图进行拓扑排序，即将 C 放在 B 的前面，那么就会出现问题。因为在这个情况下，C 是在 B 的前面的，但是 D 和 E 又依赖于 B 和 C，会导致它们无法正确排序。因此，在拓扑排序时，必须避免这种情况的发生。

结论

在有向图的拓扑排序中，如果有一条边从节点 A 指向节点 B，但是 A 又依赖于 B，那么 A 必须放在 B 的后面。如果出现环路，无法进行拓扑排序。