## Depth-First Ordering

**Introduction**: A depth-first search of a graph visits all the nodes in the graph once, by starting at the entry node and visiting the nodes as far away from the entry node as quickly as possible. The route of the search in a depth-first search forms a depth-first spanning tree (DFST). A preorder traversal visits a node before visiting any of its children, which it then visits recursively in left-to-right order. Also, a postorder traversal visits a node's children, recursively in left-to-right order, before visiting the node itself.

There is one more variant ordering that is important for flow-graph analysis: a depth-first ordering is the reverse of a postorder traversal. That is, in a depth first ordering, we visit a node, then traverse its rightmost child, the child to its left, and so on. However, before we build the tree for the flow graph, we have choices as to which successor of a node becomes the rightmost child in the tree, which node becomes the next child, and so on. Before we give the algorithm for depth-first ordering, let us consider an example.

**Example:** One possible depth-first presentation of the flow graph in Fig. 9.38 is illustrated in Fig. 9.42. Solid edges form the tree; dashed edges are the other edges of the flow graph. A depth-first traversal of the tree is given by: 1 -> 3 ->• 4 -» 6 -> 7 -»• 8 ->• 10, then back to 8, then to 9. We go back to 8 once more, retreating to 7, 6, and 4, and then forward to 5. We retreat from 5 back to 4, then back to 3 and 1. From 1 we go to 2, then retreat from 2, back to 1, and we have traversed the entire tree.

The preorder sequence for the traversal is thus

1,3,4,6,7,8,10,9,5,2.

The postorder sequence for the traversal of the tree in Fig. 9.42 is

1 0 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 .

The depth-first ordering, which is the reverse of the postorder sequence, is

1,2,3,4,5,6,7,8,9,10.

We now give an algorithm that finds a depth-first spanning tree and a depth-first ordering of a graph. It is this algorithm that finds the DFST in Fig. 9.42 from Fig. 9.38.

**Algorithm:** Depth-first spanning tree and depth-first ordering.

**INPUT:** A flow graph G.

**OUTPUT:** A DFST T of G and an ordering of the nodes of G.

**METHOD**: We use the recursive procedure search (n) of Fig. 9.43. The algorithm initializes all nodes of G to "unvisited," then calls search (no), where no is the entry. When it calls search (n), it first marks n "visited" to avoid adding n to the tree twice. It uses c to count from the number of nodes of G down to 1, assigning depth-first numbers dfn[n] to nodes n as we go. The set of edges T forms the depth-first spanning tree for G.

**Edges in a Depth-First Spanning Tree: **When we construct a DFST for a flow graph, the edges of the flow graph fallinto three categories.

1. There are edges, called advancing edges, that go from a node m to a proper descendant of m in the tree. All edges in the DFST itself are advancing edges. There are no other advancing edges in Fig. 9.42, but, for example, if 4 —>• 8 were an edge, it would be in this category.

2. There are edges that go from a node m to an ancestor of m in the tree (possibly to m itself). These edges we shall term retreating edges. For example, 4 - > 3 , 7 - > 4 , 1 0 - » 7 and 9 ->• 1 are the retreating edges in Fig. 9.42.

- void search(n) {
- mark n "visited";
- for (each successor s of n)
- if (s is "unvisited") {
- add edge n —>• s to T;
- search(s);
- }
- dfn[n] = c;
- c = c - 1;
- }
- mainQ {
- T = 0; /* set of edges */
- for (each node n of G)
- mark n "unvisited";
- c = number of nodes of G;
- search(no);
- }

**Figure 9.43: Depth-first search algorithm**

3. There are edges m —> n such that neither m nor n is an ancestor of the other in the DFST. Edges 2 - ^ 3 and 5 -> 7 are the only such examples in Fig. 9.42. We call these edges cross edges. An important property of cross edges is that if we draw the DFST so children of a node are drawn \ from left to right in the order in which they were added to the tree, thenall cross edges travel from right to left.

It should be noted that m ->• n is a retreating edge if and only if dfn[m] > dfn[n]. To see why, note that if m is a descendant of n in the DFST, then search(m) terminates before search(n), so dfn[m] > dfn[n]. Conversely, if dfn[m] > dfn[n], then search(m) terminates before search(n), or m = n. But search(n) must have begun before search(m) if there is an edge m —> n, or else the fact that n is a successor of m would have made n a descendant of m in the DFST. Thus the time search(m) is active is a subinterval of the time search(n) is active, from which it follows that n is an ancestor of m in the DFST.