![](https://csdnimg.cn/release/download_crawler_static/10607518/bg14.jpg)
16 CHAPTER 1. DEPTH-FIRST WALKS
To be pr ec is e , σ is managed as follows: As each node is first reached, it is pushed on σ. (That is, the
nodes of G are pushed on σ in pre-order .) Thus the desc en dants of each node lie above the node on σ.
In particular, the roots of the strongly connected components of G will eventually be on σ with the other
elements of their c omponent above them. When the processing (i.e. in the d ep th -fi r s t walk) for a root r is
finished, we pop every element in th e stack down to and including r. (For this to happen, of course, we have
to be able to identify the nodes which are roots of strongly connected regions. We deal with this below.)
No other elements of other strongly connected regions can be among the elements popped. This is because
if y were such an element, it would have been placed on the stack after r was first reached and before the
processing of r was finished, and so would be a descendant of r. So by the preceding lemma, the root s of
the component of y would also be a descendant of r, and so would have been placed above r on the stack.
Since its pr ocessing would have been finished before r’s proces s in g, s and all nodes higher than it on the
stack, including y, would already have been popped off the stack before we pop r.
As noted above, for this algorithm to work, we have to b e able to identify the roots of the strongly connected
regions. Using the stack σ, we can do this as follows: for each node x being processed, compute the attribute
L[x] (L is the replacement for L above), whose value is defined to be th e lesser of pre[x] and the minimum
of pre[y] taken over all y such that there is a path x = x
0
→ x
1
→ . . . → x
n
→ y where
1. Each arc up to x
n
is a tree arc.
2. The arc x
n
→ y is a back arc or a cross arc.
3. y is on σ at some point durin g the processing of x.
Here condition 3 substitutes for the pr ev ious condition 1.
The same argument as in Lemma 1.17 shows that if x is not a root, then L[x] < pre[x].
On the other hand, l et r be a root, and let y be th at node for which pre[y] = L(r). Now the only way
we could have L[r] < pre[r] is if the y belonged to a strongly connected component with root s such that
rpost[s] > rpost[r]. S in ce we also have pre[s] ≤ pre[y] = L(r) < pre[r], we have
start[s] < start[r]
finish[s] < finish[r]
and so by the parenthesis nesting property, finish[s] < start[r]; i.e., the processing of s is finished before the
processing of r starts, which means that s (and hence y) is not on the stack at any time during the processing
of r. Hence L[r] = pre[r].
Thus in the algorithm, we compute L[x] for each node as it is processed. When the processing of the no de is
finished, if L[x] = pre[x], it is known to be a root, and it and all elements above it on the stack are popped
and constitute a strongly connected component.
The complete algorithm is shown in Figure 1.9. Figure 1.10 shows the order in which the str ongly connected
components of the graph in Figure 1.8 ar e discovered, with the same depth-first walk as in that figure.