DFS实现拓扑排序
我本来设想的是将DFS逆拓扑排序的结果颠倒一下（通过栈），就可得到拓扑排序的结果。王道书给的答案是添加一个时间变量time，每次只要visit一个顶点，就time++，最后按time从小到大排序即可。
知乎上有人说：
拓扑排序得到的是各顶点的最早发生时间，
逆拓扑排序得到的是最迟发生时间。 这两个结果不能简单的颠倒得出。
我有点迷惑了，到底拓扑排序的结果颠倒一下是不是逆拓扑排序的结果呢？ 当然不是
拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
* 每个顶点出现且只出现一次。
* 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面
逆拓扑排序
* 从有向图中选择一个出度为0的顶点输出
* 删除1中的顶点，并且删除指向该顶点的全部边
* 重复上述两步，直到剩余的图中不存在出度为0的顶点为止 Hello. 发表于 2020-7-9 20:45
当然不是
拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
从概念上讲确实不一样，可是从你举的这个例子来看，拓扑排序的结果颠倒一下就是逆拓扑排序的结果。您能举一个颠倒后结果不符合的例子吗？ 可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。
前提是使用栈来存放拓扑序列，因此只要按顺序出栈就是逆拓扑序列！
如果有帮助请设置最佳^_^ Hello. 发表于 2020-7-9 20:45
当然不是
拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
听同学说拓扑学比较难，我还不知道拓扑是啥。{:10_250:}拓扑难吗 小甲鱼的铁粉 发表于 2020-7-9 23:01
听同学说拓扑学比较难，我还不知道拓扑是啥。拓扑难吗
还好还好{:10_256:}
页:
[1]