DFS算法是怎么实现逆拓扑排序的？

Question

有向图DFS算法是怎么实现逆拓扑排序的？ 不是很懂其中的实现过程 麻烦讲的通俗易懂一点

Answer 1

深度优先遍历图

1. 将出度为0的结点设置为已访问
2. 并且，若一个结点的所有下一结点均已访问，则将其设为已访问

如 a->b, a->c, b->c, b->e：

1. 深度优先a-b-c，c出度为0，输出c
2. 退回一个结点到b，访问e，e出度为0，输出e
3. 退回上一结点b，b的两个下一结点（c、e）均已访问，则将b输出，b设置为已访问
4. 退回上一结点a，a的两个下一结点（b、c）均已访问，则将a输出，a设置为已访问
   至此遍历完毕，逆拓扑排序：c-e-b-a