Java Reference
In-Depth Information
which is a collection of trees. Thus we merely maintain each connected com-
ponent in the spanning forest as a disjoint set. Initially, each vertex is in its
own disjoint set. If
u
and
v
are in the same disjoint set, as determined by two
find
operations, the edge is rejected because
u
and
v
are already connected.
Otherwise, the edge is accepted and a
union
operation is performed on the two
disjoint sets containing
u
and
v,
in effect, combining the connected compo-
nents. This result is what we want because once edge (
u, v
) has been added to
the spanning forest, if
w
was connected to
u
and
x
was connected to
v, x
and
w
must be connected and thus belong in the same set.
The test for cycles
is done by using a
union/find data
structure.
24.2.3
application: the nearest
common ancestor problem
Another illustration of the union/find data structure is the off line
nearest com-
mon ancestor
(NCA)
problem.
offline nearest common ancestor problem
Given a tree and a list of pairs of nodes in the tree, find the nearest common
ancestor for each pair of nodes.
As an example, Figure 24.8 shows a tree with a pair list containing five
requests. For the pair of nodes
u
and
z,
node
C
is the nearest ancestor of both. (
A
and
B
are also ancestors, but they are not the closest.) The problem is offline
because we can see the entire request sequence prior to providing the first
answer. Solution of this problem is important in graph theory applications and
computational biology (where the tree represents evolution) applications.
Solution of the
NCA is important in
graph algorithm
and computational
biology applica-
tions.
The algorithm works by performing a postorder tree traversal. When we
are about to return from processing a node, we examine the pair list to deter-
mine whether any ancestor calculations are to be performed. If
u
is the current
A postorder tra-
versal can be
used to solve
the problem.
figure 24.8
The nearest common
ancestor for each
request in the pair
sequence (
x, y
), (
u, z
),
(
w, x
), (
z, w
), and
(
w, y
) is
A, C, A, B,
and
y
,
respectively.
A
B
x
y
C
w
u
D
z
Search WWH ::
Custom Search