Editing Depth-first search (section)

===Vertex orderings===
It is also possible to use depth-first search to linearly order the vertices of a graph or tree. There are four possible ways of doing this:

* A '''preordering''' is a list of the vertices in the order that they were first visited by the depth-first search algorithm. This is a compact and natural way of describing the progress of the search, as was done earlier in this article. A preordering of an [[parse tree|expression tree]] is the expression in [[Polish notation]].
* A '''postordering''' is a list of the vertices in the order that they were ''last'' visited by the algorithm. A postordering of an expression tree is the expression in [[reverse Polish notation]].
* 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.

For [[binary trees]] there is additionally '''in-ordering''' and '''reverse in-ordering'''.

For example, when searching the directed graph below beginning at node A, the sequence of traversals is either A B D B A C A or A C D C A B A (choosing to first visit B or C from A is up to the algorithm). Note that repeat visits in the form of backtracking to a node, to check if it has still unvisited neighbors, are included here (even if it is found to have none). Thus the possible preorderings are A B D C and A C D B, while the possible postorderings are D B C A and D C B A, and the possible reverse postorderings are A C B D and A B C D.

: [[File:If-then-else-control-flow-graph.svg|alt=A directed graph with edges AB, BD, AC, CD]]

Reverse postordering produces a [[topological sorting]] of any [[directed acyclic graph]]. This ordering is also useful in [[control-flow graph|control-flow analysis]] as it often represents a natural linearization of the control flows. The graph above might represent the flow of control in the code fragment below, and it is natural to consider this code in the order A B C D or A C B D but not natural to use the order A B D C or A C D B.

 if ('''A''') then {
     '''B'''
 } else {
     '''C'''
 }
 '''D'''