Editing Depth-first search (section)

==Output of a depth-first search==
[[File:Tree edges.svg|thumb|upright=1.2|The four types of edges defined by a spanning tree]]
The result of a depth-first search of a graph can be conveniently described in terms of a [[spanning tree (mathematics)|spanning tree]] of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: '''forward edges''', which point from a node of the tree to one of its descendants, '''back edges''', which point from a node to one of its ancestors, and '''cross edges''', which do neither. Sometimes '''tree edges''', edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

===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'''