0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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:

A sample graph

Link to source (archive of image used in original post)

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.

$\endgroup$
  • 3
    $\begingroup$ This answer seems to assume there is only one possible postorder ("the" postorder), but that's not the case: depending on what order DFS makes certain choices, you can get different postorders. To prove the point you want to make, I think you need to list all possible postorders, rather than just one. $\endgroup$ – D.W. Jul 23 '16 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.