对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是 （）
image
A、3,1,2,4,5,6 B、3,1,2,4,6,5
C、3,1,4,2,5,6 D、3,1,4,2,6,5
Q：什么是拓扑排序（Topological Sort）？
A：简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
让我们一起来回顾离散数学中关于偏序和全序的定义：
若集合 X 上的关系 R 是自反的、反对称的和传递的，则称 R 是集合 X 上的偏序关系。
设 R 是集合 X 上的偏序（Partial Order），如果对每个 x，y∈X 必有 xRy 或yRx，则称 R 是集合 X 上的全序关系。
Q： 还不是很懂啊？！
A：直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
例如，下图所示的两个有向图图中弧（x，y）表示 x≤y，则（a）表示偏序，（b）表示全序。
image
若在（a）的有向图上人为地加一个表示v2≤v3 的弧（符号 ≤ 表示 v2 领先于边 v3），则（a）表示的亦为全序，且这个全序称为拓扑有序，而由偏序定义得到拓扑有序的操作便是拓扑排序。
Q：嗯嗯，明白了呢。那么，又该如何进行拓扑排序呢？
A：方法其实很简单：
（1）在有向图中选一个没有前驱的顶点且输出之。
（2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
Q：能不能举个栗子呢？
A：好吧，以下面的有向图为例。
image
图中，v1 和 v6 没有前驱，则可任选一个。假设先输出 v6，在删除 v6 及弧（v6，4），（v6，v5）之后，只有顶点 v1 没有前驱，则输出 v1 且删去 v1 及弧 （v1，v2）、（v1，v3）和（v1,v4），之后v3 和 v4 都没有前驱。
依次类推，可从中任选一个继续进行。整个拓扑排序过程如上图所示。
最后得到该有向图的拓扑有序序列为（注意：拓扑排序序列不一定唯一）：
v6 - v1 -v4 - v3 - v2 - v5
A：讲到这里，相信大家对拓扑排序应该有个大概的了解了吧，那么上面题目的答案就由你们自己推理啦。
文章首发于公众号【暗星涌动】。
网友评论