[已解决]DFS实现拓扑排序

茶叶仓鼠

我本来设想的是将DFS逆拓扑排序的结果颠倒一下（通过栈），就可得到拓扑排序的结果。

王道书给的答案是添加一个时间变量time，每次只要visit一个顶点，就time++，最后按time从小到大排序即可。

知乎上有人说：
拓扑排序得到的是各顶点的最早发生时间，
逆拓扑排序得到的是最迟发生时间。 这两个结果不能简单的颠倒得出。

我有点迷惑了，到底拓扑排序的结果颠倒一下是不是逆拓扑排序的结果呢？

最佳答案

月排行榜 / 总排行榜

Hello.

2020-7-9 21:07:30

可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。

前提是使用栈来存放拓扑序列，因此只要按顺序出栈就是逆拓扑序列！

如果有帮助请设置最佳^_^

跳转到最佳答案楼层

Hello.

当然不是

拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：

* 每个顶点出现且只出现一次。
* 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面

逆拓扑排序
* 从有向图中选择一个出度为0的顶点输出
* 删除1中的顶点，并且删除指向该顶点的全部边
* 重复上述两步，直到剩余的图中不存在出度为0的顶点为止

茶叶仓鼠

Hello. 发表于 2020-7-9 20:45
当然不是

拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：

从概念上讲确实不一样，可是从你举的这个例子来看，拓扑排序的结果颠倒一下就是逆拓扑排序的结果。您能举一个颠倒后结果不符合的例子吗？

Hello.

可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。

前提是使用栈来存放拓扑序列，因此只要按顺序出栈就是逆拓扑序列！

如果有帮助请设置最佳^_^

小甲鱼的铁粉

Hello. 发表于 2020-7-9 20:45
当然不是

拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：

听同学说拓扑学比较难，我还不知道拓扑是啥。拓扑难吗

Hello.

小甲鱼的铁粉 发表于 2020-7-9 23:01
听同学说拓扑学比较难，我还不知道拓扑是啥。拓扑难吗

还好还好