[Solved]: Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

Problem Detail: 

I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems that we get the reverse of topological order, so at first I thought that it's the same, but then I looked on his website and he answers "False".

If you think about it, in postorder of a digraph, we first visit every child of the vertex and add it to some queue, hence since the children are visited first, we get the order which is the reverse of topological.

Why does Sedgewick say they're not the same?

Asked By : Pavel

Answered By : Shubham Mittal

I wrote a short example to test the hypothesis and found out that the reverse postorder of a reverse graph is indeed not the same as the postorder of the original graph.
Consider the following graph:

Postorder for the above graph is: 0 1 3 2 4 5.

Postorder for the reverse graph is: 4 5 0 2 3 1.

Reverse Postorder for the reverse graph is: 1 3 2 0 5 4.

You are thinking on the correct lines, but what we should understand is that the postorder of a graph is not necessarily the reverse of the postorder of the reverse graph. This is because of the way we iterate over the vertices when calling the depth-first search. There could be different solutions to the same problem, given the iteration method is different.

And because of this, the reverse postorder of a digraph's reverse is not necessarily the same as the postorder of the digraph.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47298