by Kevin Wayne, Robert Sedgewick Okay, so the first step is to be able to make some observations about the running time of the programs. And for analysis of algorithms that’s easier than in a lot of scientific disciplines, as…

Weiqiang's Tech Blog
Interesting in Web Development and Multimedia Technology

All right so QuickFind is too slow for huge problems. So, how are we going to do better? Our first attempt is an alternative called, Quick-union. This is so called lazy approach to algorithm design where we try to avoid doing work until we have to. It uses the same data structure or array ID with size M but now it has a different interpretation. We are going to think of that array as representing a set of trees that’s called a forest as depicted at right. So, each entry in the array is going to contain a reference to its parent in the tree. So, for example, 3’s parent is four, 4’s parent is nine. So 3’s entry is four and 4’s entry is nine in the array. Now each entry in the array has associated with it a root. That’s the root of its tree.

Now we’ll look at our first implementation of an algorithm for solving the dynamic connectivity problem, called Quick-find.

This is a so called eager algorithm, for solving kind activity problem. The data structure that we’re going to use to support the algorithm is simply an integer array indexed by object. The interpretation is the two objects, P and Q are connected if and only if, their entries in the array are the same.

So for example in this example with our ten objects the idea array that describes the situation after seven connections is illustrated in the middle of the slide. So that, after the, at this point zero, five, and six are all in the same connected component, because they have the same array entry, zero. One, two, and seven all have entry one. And three, four, eight, and nine all have entry eight.

Welcome back to algorithms. Today, we’re going to talk about the union find problem. A set of algorithms for solving the so-called dynamic connectivity problem. We’ll look at two classic algorithms. Quick Find and Quick Union, and some applications and improvements of those algorithms. The subtext of today’s lecture really is to go through the steps that we’ll follow over and over again to develop a useful algorithm. The first step is to model the problem. Try to understand, basically, what are the main elements of the problem that need to be solved. Then we’ll find some algorithm to solve the problem.