A Note of Union Find
Basic
- What is it
A data structure that classify nodes to different sets -> when adding and edge(two vertex) you find they are already in a set, it mean there is a cycle.
Also called disjoint set.
- Why use it
Constant space and time complexity. The key of union find is the efficiency of union() and find()
The precedency of minimum spanning tree.
-
The procedure of build such structure
https://youtu.be/YKE4Vd1ysPI
- At first each node are not connect others
- If two nodes are connected, let one be the parent of the other ;
Implementation
Basic
package Graph.unionfind;
public interface IUnionFind {
int count(); // how many nodes
int union(int x, int y); // merge nodes;
int find(int x); // find the corresponded set;
boolean connected(int x, int y); // if two nodes connected;
}
package Graph.unionfind;
public class UnionFindImpl implements IUnionFind{
int count;
private int[] id;
public UnionFindImpl(int count) {
this.count = count;
id = new int[count];
for (int i = 0; i < count; i++) {
id[i] = i;
}
}
@Override
public int count() {
return count;
}
@Override
public void union(int x, int y) {
int A = find(x);
int B = find(y);
if (A == B) {
return;
}
for (int i = 0; i < count; i++) {
if (id[i] == A) {
id[i] = B;
}
}
}
@Override
public int find(int x) {
return id[x];
}
@Override
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
Forest Tree representation
Quick Union
Build a tree , connected nodes share same root.
package Graph.unionfind;
public class QuickUnion implements IUnionFind{
int count;
private int[] parent;
public QuickUnion(int count) {
this.count = count;
parent = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
}
}
@Override
public int count() {
return count;
}
@Override
public void union(int x, int y) {
// build a tree
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
parent[xRoot] = yRoot;
}
@Override
public int find(int x) {
// find the root;
while (x != parent[x]) {
x = parent[x];
}
return x;
}
@Override
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
Balance Optimization
Sometimes, the tree may not balance very well and the traverse time become worst O(n) rather than O(logn).
Quick Find Union by Weight
package Graph.unionfind;
public class QuickFindUnionByWeight implements IUnionFind{
int count;
private int[] parent;
private int[] size;
public QuickFindUnionByWeight(int count) {
this.count = count;
parent = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
size[i] = 1;
}
}
@Override
public int count() {
return count;
}
@Override
public void union(int x, int y) {
// light weight merge to heavy ones;
int xRoot = find(x);
int yRoot = find(y);
if (size[xRoot] > size[yRoot]) {
parent[yRoot] = xRoot;
size[xRoot] += size[yRoot];
} else {
parent[xRoot] = yRoot;
size[yRoot] += size[xRoot];
}
}
@Override
public int find(int x) {
while (x != parent[x]) {
x = parent[x];
}
return x;
}
@Override
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
Quick Find Union by Rank
package Graph.unionfind;
public class QuickFindUnionByRank implements IUnionFind{
int count;
private int[] parent;
private int[] rank;
public QuickFindUnionByRank(int count) {
this.count = count;
parent = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int count() {
return count;
}
@Override
public void union(int x, int y) {
// lower rank merge to higher ones;
int xRoot = find(x);
int yRoot = find(y);
if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else if (rank[xRoot] < rank[yRoot]){
parent[xRoot] = yRoot;
} else {
parent[xRoot] = yRoot;
rank[yRoot]++;
}
}
@Override
public int find(int x) {
while (x != parent[x]) {
x = parent[x];
}
return x;
}
@Override
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
Path Compression
Why we are doing this? Because we actually only care about what the root is each tree. So we are thinking if we could compression the height of the tree and keep it a constant?
Yes we can. There are two ways
package Graph.unionfind;
public class QuickFindPathCompression implements IUnionFind{
int count;
private int[] parent;
public QuickFindPathCompression(int count) {
this.count = count;
parent = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
}
}
@Override
public int count() {
return count;
}
@Override
public void union(int x, int y) {
// quick union, pass
}
@Override
public int find(int x) { // pick one of find or find2
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int find2(int x) {
if (x != parent[x]) {
parent[x] = find2(parents[x]); // find the root recursively, more aggressive, make the root as father and all the other nodes, children
}
return parent[x];
}
@Override
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
If you do the second path compression, you may notice balance does not matter anymore so if you use second path compression, you don't need do the balance by size in the union.