8.6.5 Depth-First Order and Depth-First Spanning Trees

Intuitively, we begin at the start node and attempt to get as far away as possible. As we proceed, we can make a (yet another!) tree from the arcs of the flow graph. This is called a depth-first spanning tree, DFST.

A depth-first order is defined to be the reverse of the order in which we last visit the nodes of the control graph when we create the DFST. The following algorithm creates a depth-first spanning tree.

Algorithm

DFST

 T := empty
 n := Start node
 REPEAT
 	IF n has an unmarked successor s THEN
 	BEGIN
 		Add n  s to T
 		Mark s
 		n := s
 	END
 	ELSE
 		n := parent of n in T
 UNTIL n = start node and n has no unmarked successors

Exercise 4 asks the readers to compute dominators by visiting the nodes in a somewhat random order and then to compute dominators by visiting the nodes in a depth-first order. For some graphs, the algorithm terminates faster when the nodes are visited in a depth-first order than when they are visited in the order Start, Node A, Node B, Node C, Node D.