Problem: Given disjoint sets of objects, we need to support following two methods:
- Find: Are two objects are in the same set.
- Union: Replace sets containing two items by their union.
Goal is to efficiently implement above two methods.
Algorithm and Implementations:
1. Quick-Find: Have an array of integers say id of size N. We can say that P and Q are connected if they have same id i.e. id[P] is equal to id[Q] then we can say P and Q are connected. For example:
In the above image 2, 3, 4 and 9 are connected and also 5 and 6 are connected so the disjoint sets are:
{0}, {1}, {2,3,4,9}, {5,6}, {7}, {8}
Let's see the algorithm of the two methods:
- Find: Check if id[P] and id[Q] are same. Complexity: O(1)
- Union: Change all entries with id[p] to id[Q]. Complexity: O(n). For example if we need to do union of 4 and 5 in the above image then it will look like:
Implementation in C#:
public class QuickFind
{
private int[] id;
public QuickFind(int size)
{
this.id = new int[size];
for (int i = 0; i < size; ++i)
{
this.id[i] = i;
}
}
public bool Find(int p, int q)
{
return this.id[p] == this.id[q];
}
public void Union(int p, int q)
{
int targetId = this.id[p];
for(int i = 0; i < id.Length; ++i)
{
if (this.id[i] == targetId)
{
this.id[i] = this.id[q];
}
}
}
}
2. Quick-Union: id[i] is the parent of i and Root of i is id[id[id[...id[i]...]]], basically keep doing it until it doesn't change.
For the above image our id array will look like:
Algorithm for the methods:
- Find: Root(p) == Root(q). Complexity will be depth of p and q in the tree. Worst case O(n).
- Union: id[Root(p)] = Root(q). Complexity is same as find hence worst case O(n). Union of 3 and 5 in the above image will look like:
and after union our id array will look like:
Implementation in C#:
public class QuickUnion
{
private int[] id;
public QuickUnion(int size)
{
this.id = new int[size];
for (int i = 0; i < size; ++i)
{
this.id[i] = i;
}
}
public bool Find(int p, int q)
{
return this.Root(p) == this.Root(q);
}
public void Union(int p, int q)
{
int rootP = this.Root(p);
int rootQ = this.Root(q);
this.id[rootP] = rootQ;
}
private int Root(int i)
{
while (this.id[i] != i)
{
i = this.id[i];
}
return i;
}
}
3. Weighted Quick-Union: The problem with the Quick-Union approach was that the tree could become very tall. That's why the find and union becomes expensive. In this approach we keep track of size of each set and while doing union we link small size tree to larger one. Here are the algorithms:
- Find: Same as Quick-Union.
- Union: We maintain an array say sizeofSets. We find Root(p) and Root(q) like Quick-Union. Now if sizeOfSets[Root(p)] is lesser than sizeOfSets[Root(q)] then set id[Root(p)] = Root(q) otherwise set id[Root(q)] = Root(p). We also set the sizeOfSets according to union.
Now given that we are not making tall trees. We are making sure that the trees are as small as possible. The depth of p and q will be no more than log(n). That means complexity of both the above methods will be O(logn).
Implementation in C#:
public class WeightedQuickUnion
{
private int[] id;
private int[] sizeOfSets;
public WeightedQuickUnion(int size)
{
this.id = new int[size];
this.sizeOfSets = new int[size];
for (int i = 0; i < size; ++i)
{
this.id[i] = i;
this.sizeOfSets[i] = 1;
}
}
public bool Find(int p, int q)
{
return this.Root(p) == this.Root(q);
}
public void Union(int p, int q)
{
int rootP = this.Root(p);
int rootQ = this.Root(q);
if (this.sizeOfSets[rootP] <= this.sizeOfSets[rootQ])
{
this.id[rootP] = rootQ;
this.sizeOfSets[rootQ] += this.sizeOfSets[rootP];
}
else
{
this.id[rootQ] = rootP;
this.sizeOfSets[rootP] += this.sizeOfSets[rootQ];
}
}
private int Root(int i)
{
while (this.id[i] != i)
{
i = this.id[i];
}
return i;
}
}
We can still do some improvements like path compression. That is while finding the Root we can assign i's parent to i's grandparent so the Root method will look like:
private int Root(int i)
{
while (this.id[i] != i)
{
id[i] = id[id[i]];
i = this.id[i];
}
return i;
}
In that way we will have to traverse less. However the worst complexity will remain same.
That's all!
No comments:
Post a Comment