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

result of this operation, the sets containing cells 18 and 13 are combined by
a union operation. The reason is that all the cells previously connected to 18
are now connected to all the cells previously connected to 13. At the end of
the algorithm, as depicted in Figure 24.5, all the cells are connected, and we
are done.
The running time of the algorithm is dominated by the union/find costs.
The size of the union/find universe is the number of cells. The number of find
operations is proportional to the number of cells because the number of
removed walls is 1 less than the number of cells. If we look carefully, how-
ever, we can see that there are only about twice as many walls as cells in the
first place. Thus, if N is the number of cells and as there are two find s per ran-
domly targeted wall, we get an estimate of between (roughly) 2 N and 4 N find
operations throughout the algorithm. Therefore the algorithm's running time
depends on the cost of O ( N ) union and O ( N ) find operations.

24.2.2 application: minimum spanning trees

A spanning tree of an undirected graph is a tree formed by graph edges that
connect all the vertices of the graph. Unlike the graphs in Chapter 14, an edge
( u, v ) in a graph G is identical to an edge ( v, u ). The cost of a spanning tree is
the sum of the costs of the edges in the tree. The minimum spanning tree is a
connected subgraph of G that spans all vertices at minimum cost. A minimum
spanning tree exists only if the subgraph of G is connected. As we show
shortly, testing a graph's connectivity can be done as part of the minimum
spanning tree computation.
In Figure 24.6(b), the graph is a minimum spanning tree of the graph in
Figure 24.6(a) (it happens to be unique, which is unusual if the graph has
many edges of equal cost). Note that the number of edges in the minimum
spanning tree is

The minimum
spanning tree is a
connected sub-
graph of G that
spans all vertices at
minimum total cost.

V - 1. The minimum spanning tree is a tree because it is

figure 24.5
Eventually, 24 walls
have been knocked
down, and all the
elements are in the
same set.

012 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24}