什么是逆后序?

What is the reverse postorder?

维基百科上是这样解释的:Data-flow analysis

This is a typical iteration order for forward data-flow problems. In reverse-postorder iteration, a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that this is not the same as preorder.)

有人可以更详细地解释一下吗?

顾名思义,反向后序产生与后序遍历完全相反的结果。

示例

对于上面提到的有向图

后序遍历为 D B C A 和 D C B A

反向后序遍历是A C B D和A B C D

如何获得反向后序遍历

一种方法是运行后序遍历并按后序将节点压入堆栈。

然后弹出节点得到反向后序。

申请

使用深度优先搜索的拓扑排序。