The disjoint set class - Data Structures and Problem Solving Using Java - page 925

that connects a tree node with a nontree node. An implementation of
Prim's algorithm is essentially identical to Dijkstra's shortest-path
algorithm given in Section 14.3, with an update rule:

d w = min d w c vw ( , )

,

(instead of . Also, as the graph is undirected,
each edge appears in two adjacency lists. Implement Prim's algorithm
and compare its performance to that of Kruskal's algorithm.

d w =min d w d v ( , + c vw ) )

,

Write a program to solve the offline NCA problem for binary trees.
Test its efficiency by constructing a random binary search tree of
10,000 elements and performing 10,000 ancestor queries.

24.18

references

Representation of each set by a tree was proposed in [8]. [1] attributes path
compression to McIlroy and Morris and contains several applications of the
union/find data structure. Kruskal's algorithm is presented in [11], and the
alternative discussed in Exercise 24.17 is from [12]. The NCA algorithm is
described in [2]. Other applications are described in [15].
The O ( M log*N) bound for the union/find problem is from [9]. Tarjan
[13] obtained the O ( M α ( M, N )) bound and showed that the bound is tight.
That the bound is intrinsic to the general problem and cannot be improved
by an alternative algorithm is demonstrated in [14]. A more precise bound
for M < N appears in [3] and [16]. Various other strategies for path compres-
sion and union achieve the same bounds; see [16] for details. If the sequence
of union operations is known in advance, the union/find problem can be
solved in O ( M ) time [7]. This result can be used to show that the offline
NCA problem is solvable in linear time.
Average-case results for the union/find problem appear in [6], [10], [17],
and [5]. Results bounding the running time of any single operation (as
opposed to the entire sequence) are given in [4].

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of
Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

1.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “On Finding Lowest Com-
mon Ancestors in Trees,” SIAM Journal on Computing 5 (1976), 115-132.

2.

L. Banachowski, “A Complement to Tarjan's Result about the Lower
Bound on the Set Union Problem,” Information Processing Letters 11
(1980), 59-65.

3.