Union-find approach - quick-find
Keywords: | union-find, quick-find, algorithms |
Date: |
- The data structure for this approach is as follows:
- integer array
id[N]
N
is equal to the number of objects in the disjoint set- each index of
id[]
corresponds to an object in the disjoint set
- each index of
- each value in
id[]
denotes the root/representative element of the set/component containing that particular object
- interpretation:
p
andq
are connected if and only if they have the sameid
- integer array
id[10]{0, 1, 1, 8, 8, 0, 0, 1, 8, 8}
// connected sets:
// {0, 5, 6}
// {1, 2, 7}
// {3, 4, 8, 9}
Find
:- Check if
p
andq
have the sameid
- Check if
Union
:- To merge components containing
p
andq
, change all entries whoseid
==id[p]
toid[q]
- To merge components containing
Example implementation
public class QuickFindUF
{
private int[] id;
public QuickFindUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public boolean connected(int p, int q)
{
return id[p] == id[q];
}
public void union(int p, int q)
{
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
Problem: too slow (algorithm is quadratic)
- for each
new
andunion()
operation, the array is accessedN
times (thefor
loops)- we only use
init()
once, butunion()
is certainly too expensive:N^2
array accesses are required to executeN
union commands onN
objects
- we only use
Cost:
new
:N
Union
:N
Find
: 1