Are preorder DFS and postorder DFS of a graph reverse to each other? Are preorder DFS and postorder DFS of a graph reverse to each other?
https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings says no:


*

*A reverse preordering is the reverse of a preordering, i.e. a list of the vertices in the opposite order of their first visit. Reverse
preordering is not the same as postordering.


*A reverse postordering is the reverse of a postordering, i.e. a list of the vertices in the opposite order of their last visit. Reverse
postordering is not the same as preordering.

I believe yes, with an addition to reverse the traversal order between children of a vertex. My reasoning is based on CLRS' Introduction of Algorithms 3ed

22.3 Depth-ﬁrst search
Another important property of depth-ﬁrst search is that discovery and
ﬁnishing times have parenthesis structure. If we represent the
discovery of vertex u with a left parenthesis “(u” and represent its
ﬁnishing by a right parenthesis “u)”, then the history of discoveries
and ﬁnishings makes a well-formed expression in the sense that the
parentheses are properly nested. For example, the depth-ﬁrst search of
Figure 22.5(a) corresponds to the parenthesization shown in Figure
22.5(b). The following theorem provides another way to characterize the parenthesis structure.
Theorem 22.7 (Parenthesis theorem) In any depth-ﬁrst search of a (directed or undirected) graph G = (V,E), for any two vertices u and v, exactly one of the following three conditions holds:

*

*the intervals [u.d, u.f] and [v.d, v.f] are entirely disjoint, and neither u nor v is a descendant of the other in the depth-ﬁrst forest,

*the interval [u.d, u.f] is contained entirely within the interval [v.d, v.f], and u is a descendant of v in a depth-ﬁrst tree, or

*the interval [v.d, v.f] is contained entirely within the interval [u.d, u.f], and v is a descendant of u in a depth-ﬁrst tree.


Thanks.
 A: The Wikipedia example explains it well : the postorderings always put D at first (so, in reverse order, at the end) while the preorderings always put it in the middle.
Your idea works with trees and with non-oriented graphs, but in oriented graphs you may have multiple paths leading to one node, and in a DFS you'll have to finish exploring that node before going back up ; and later you might have another branch coming to that point that, if you had taken it before the other, would have been prolongated. The preordering and postordering then give different versions.
With non-oriented graphs, you rule out the possibility to come back again to a node, so the set of preorderings and the set of reversed postorderings are the same.
But anyway, in general the question isn't that mush "could I have had the same string with a different algorithm and a different order of visit ?" but more "for a given DFS, that is a given order of visit, how do the preorder and the postorder interact with each other and give me information ?". This leads to a lot of nice algorithms, typically invented by Tarjan in the 70's.
