Java Reference
In-Depth Information
/
The variable
num
is global between DFST and DFS.
/
procedure
DFST(
G
f
)
num
←
0
foreach
Z
∈N
f
do
child
(
Z
)
←
null
dfn
(
Z
)
←
0
parent
(
root
)
←
null
call
DFS(
root
)
NumNodes
←
num
end
procedure
DFS(
X
)
num
←
num
+
1
dfn
(
X
)
←
num
vertex
(
num
)
←
X
foreach
Y
∈
Succ
(
X
)
do
if
dfn
(
Y
)
26
=
0
then
parent
(
Y
)
←
X
sibling
(
Y
)
←
child
(
X
)
27
←
Y
call
DFS(
Y
)
progeny
(
X
)
child
(
X
)
28
←
num
−
dfn
(
X
)
end
Figure 14.9: Depth-first numbering and spanning tree. The algorithm's
input is a flow graph
G
f
=
(
N
f
,E
f
,
root
).
Depth-first spanning tree
parent
(
Z
) are t f e
Z
child
(
Y
)
head of the list of
Y
's children
sibling
(
Z
)
next node in the list of
parent
(
Z
)'s children
Depth-first numbering
dfn
(
Z
)
the depth-first number associated with node
Z
vertex
(
n
)
the node with depth-first number
n
progeny
(
Z
)
the number of proper descendants of node
Z
in the
DFST
NumNodes
the number of nodes in
N
f
that are reachable from
root
These data structures use a constant number of references per node to represent
a tree, as described in Section 7.4.2 on page 251. Nodes in the flowgraph shown
in Figure 14.10 are already labeledwith their depth-first numbering. The DFST
