7

祝大家复活节快乐。

我目前正在学习拓扑排序，并且有一个关于拓扑排序试图真正排序的问题。

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

拓扑排序是有向无环图（DAG）上最重要的操作。它对一条线上的顶点进行排序，使得所有有向边都从左到右。

这个大胆的部分让我感到困惑。那么拓扑排序是对顶点排序还是对所有有向边排序呢？

让我们举一个书中也有的例子。

有向无环图

所以对于上面的DAG，我们可以得到一个拓扑排序（G、A、B、C、F、E、D）。

我可以理解这种类型。不仅顶点被排序，边也被排序，即G->A->B->C->F->E->D，这符合上面ADM书的描述：all directed edges go from left to right

但是如果我删除 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) 是有效排序吗？

谢谢

4

1 回答 1

9

您可以将其视为元素的排序。

让 v1,v2,...,vn 成为元素。并让一条边(vi,vj)表示vi<vj。拓扑排序保证排序后：对于每一个vi，对于每一个vj这样的i < j，vj不大于vi

或者用其他表示法：假设(vi,vj)表示vj依赖于vi，拓扑排序保证每个元素“不依赖”排序中出现在它之后的任何元素。

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

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

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

是的，您添加的每条边，只需添加一个约束。请注意，拓扑排序可能有不止一个可行的解决方案[例如，对于没有边的图，任何排列都是可行的解决方案]。消除约束，使任何以前的解决方案，“解决一个更难的问题”仍然可行。

即使 A 是 B 和 C 的父级，我们还能认为 (G, A, B, C, F, E, D) 是有效排序吗？

没有问题！A在拓扑排序中出现在B，C之前，所以没有问题是他们的父亲。

希望这让它更清楚一点。

于 2012-04-08T11:44:26.190 回答