particular to DFS trees is that all descendants of a node u are processed in the time interval from when u is discovered
to when we backtrack through it.
To make use of this property, we need to know when the algorithm is backtracking, which can be a bit hard
in the iterative version. Although you could extend the iterative DFS from Listing 5-5 to keep track of backtracking
(see Exercise 5-7), I’ll be extending the recursive version (Listing 5-4) here. See Listing 5-7 for a version that adds
timestamps to each node: one for when it is discovered (discover time, or d) and one for when we backtrack through it
(finish time, or f).
Do'stlaringiz bilan baham: |