拓扑排序是尝试对顶点还是边进行排序？

Question

大家复活节快乐。

我正在学习拓扑排序，并对拓扑排序尝试真正排序的内容有疑问。

算法设计手册这样描述拓扑排序：

拓扑排序是有向无环图（DAGs）上最重要的操作。 它将顶点按顺序排列在一条线上，使所有有向边从左到右。

这个加粗部分让我感到困惑。那么，是拓扑排序对顶点排序还是对所有有向边进行排序？

我们来看一下书中的例子。

对于上述DAG，我们可以得到一个拓扑排序(G, A, B, C, F, E, D)。

我能理解这个排序。不仅顶点被排序，边也被排序了，即G->A->B->C->F->E->D，这与上面ADM书中的描述相匹配：“所有有向边从左到右”。

但是，如果我删除B->C的边呢？生成的图仍然是一个DAG，但是拓扑排序仍然是(G, A, B, C, F, E, D)吗？

如果是的话，那么我认为边没有被排序，因为A->B->C不再存在，而是A->B和A->C。那么，在这种情况下，这仍然是一个有效的拓扑排序吗？即使A是B和C的父节点，我们仍然可以认为(G, A, B, C, F, E, D)是一个有效的排序吗？

谢谢

- Jackson Tale

Answer 1

你可以将其看作元素的排序。

假设 v1，v2，...，vn 是元素，边缘 (vi,vj) 表示 vi

换句话说：假设 (vi,vj) 表示 vj 依赖于 vi，拓扑排序保证每个元素“不依赖于”在其后出现的任何元素。

那么拓扑排序是对顶点进行排序还是对所有有向边进行排序？

拓扑排序对顶点进行排序，而不是边缘。它使用边缘作为排序顶点的约束条件。

但如果我删除 B->C 的边缘呢？

是的，您添加的每个边缘都只会添加一个约束条件。请注意，可能存在多个可行的拓扑排序解决方案 [例如，对于没有边缘的图，任何排列都是可行的解决方案]。删除约束条件使得任何先前的“解决更难问题”的解决方案仍然可行。

即使 A 是 B 和 C 的父母，我们仍然可以认为 (G,A,B,C,F,E,D) 是有效的排序吗？

这没有问题！在拓扑排序中，A 在 B、C 之前出现，因此它是它们的父亲也没有问题。

希望这样更加清晰明了。

- amit

---

那么，根据您的描述，如果我删除B->C，那么B应该在C之前还是之后？因为我们不再知道B是否比C小。 - Jackson Tale

@JacksonTale：如果你删除B->C，那么两者都是可行的解决方案！[除非我错过了某些边]就像我所提到的，拓扑排序可能有多个解决方案。 - amit

谢谢Amit的帮忙编辑，现在我理解得更加清晰了。 - Jackson Tale

@JacksonTale，许多DAG描述的集合仅部分有序（POSET），因此存在更多可能的拓扑排序。在您的示例中，如果删除B->C，则G->A->C->F->E->D仍必须按此顺序出现。B现在仅受到从A到D的边的限制，因此可以出现在它们之间的任何位置；导致4种不同的可能排序。 - voidengine

@pjotr 非常感谢。你提供的 POSET 信息确实帮助了我很多。 - Jackson Tale