if (i == j) continue;
id[i] = j;
cout << " " << p << " " << q << endl;
Program 1.2 is an implementation of the union and find operations that comprise
the quick-union algorithm to solve the connectivity problem. The quick-union
algorithm would seem to be faster than the quick-find algorithm, because it does
not have to go through the entire array for each input pair; but how much faster is
it? This question is more difficult to answer here than it was for quick find,
because the running time is much more dependent on the nature of the input. By
running empirical studies or doing mathematical analysis (see Chapter 2), we can
convince ourselves that Program 1.2 is far more efficient than Program 1.1, and
that it is feasible to consider using Program 1.2 for huge practical problems. We
shall discuss one such empirical study at the end of this section. For the moment,
we can regard quick union as an improvement because it removes quick find's
main liability (that the program requires at least NM instructions to process M
union operations among N objects).
This difference between quick union and quick find certainly represents an
improvement, but quick union still has the liability that we cannot guarantee it to
be substantially faster than quick find in every case, because the input data could
conspire to make the find operation slow.
Property 1.2. For M > N, the quick-union algorithm could take more than MN/2
instructions to solve a connectivity problem with M pairs of N objects
Suppose that the input pairs come in the order 1-2, then 2-3, then
3-4, and so forth. After N – 1 such pairs, we have N objects all in the
same set, and the tree that is formed by the quick-union algorithm is a
straight line, with N pointing to N – 1, which points to N – 2, which
points to N – 3, and so forth. To execute the find operation for object
N, the program has to follow N – 1 pointers. Thus, the average number
of pointers followed for the first N pairs is
(0 + 1 + ... + (N – 1))/N = (N – 1)/2.
Now suppose that the remainder of the pairs all connect N to some
other object. The find operation for each of these pairs involves at least
(N – 1) pointers. The grand total for the M find operations for this
sequence of input pairs is certainly greater than MN/2.
Fortunately, there is an easy modification to the algorithm that allows us to
guarantee that bad cases such as this one do not occur. Rather than arbitrarily
connecting the second tree to the first for union, we keep track of the number of
nodes in each tree and always connect the smaller tree to the larger. This change
requires slightly more code and another array to hold the node counts, as shown
in Program 1.3, but it leads to substantial improvements in efficiency. We refer to
this algorithm as the weighted quick-union algorithm.
Figure 1.7 shows the forest of trees constructed by the weighted union–find
algorithm for the example input in Figure 1.1. Even for this small example, the
Part One: Fundamentals 13
Part One: Fundamentals 13
我的内容管理
展开
