Java Reference
In-Depth Information
procedure
right
T
o
L
eft
T
raversal
(
root
)
call
visit
N
ode
(
root
)
end
procedure
visit
N
ode
(
n
)
c
←
child
(
n
)
while
c
null do
/
Preorder code goes here
/
29
call
visit
N
ode
(
c
)
/
Postorder code goes here
/
30
c
←
sibling
(
c
)
end
Figure 14.11: Right-to-left DFST traversal.
superimposed on the tree of Figure 14.12. Recall that the words
ancestor
,
de-
scendant
,and
child
refer to nodes in
tree
data structure (such as a DFST), while
the words
successor
and
predecessor
refer to nodes of a
graph
.Eachedgein
E
f
can then be uniquely described with respect to a given DFST for
G
f
as follows:
Tree:
A
tree edge
appears in both
G
f
. In Fig-
ure 14.13, the tree edges are shownwith normal, solid lines. For example,
4
E
f
and the given DFST for
→
8 is a tree edge.
Back:
A
back edge
connects a node
Y
with an ancestor
X
of
Y
. In Figure 14.13,
the back edges are shown in bold: 6
→
5, 5
→
3, and 12
→
11.
Chord:
A
chord edge
connects a node
X
with a proper descendant of
X
.In
Figure 14.13, the dotted edges 2
→
4and1
→
3 are the only chord edges.
Cross:
The remaining edges are
cross edges
. faDFSTisdrawnsothata
node's children appear left to right in order of their depth-first discovery,
then a graph's cross edges are always oriented from right to left when
superimposed on the DFST. In Figure 14.13, the cross edges are drawn
with dashes: 8
→
6, 9
→
8, 10
→
6, 12
→
7, and 13
→
12.
The data structures computed by the algorithm of Figure 14.9 su
ce to deter-
mine the type of any edge due to the following theorem:
Theorem 14.2
Node Y is in the depth-first spanning subtree rooted at X,denoted
X
Y, if and only if
dfn
(
X
)
≤
dfn
(
Y
)
≤
dfn
(
X
)
+
progeny
(
X
)
Proof: Left as Exercise 13.
