javaalgorithmunion-find

Weighted Quick-Union with Path Compression algorithm-Union Find


I have a project in which i have to implement a weighted quick-union with path compression algorithm.After seeing a number of others source code,i ended up in this:

public class UnionFind {

private int[] parent;
private int[] size;
private int maxItemCount;      // maximum number of items from {0,1,...,N-1}
private int numItems;      // number of items created

UnionFind(int N) {
    this.N = N;
    this.K = 0;
    parent = new int[N];
    size = new int[N];
    for (int i = 0; i < N; i++) {
        parent[i] = -1;
        size[i] = 0;
    }
}

void makeSet(int v) {
    if (parent[v] != -1) return; // item v already belongs in a set
    parent[v] = v;
    size[v] = 1;
    K++;
}

int find(int v) {
    if (v == parent[v]) {
        return v;
    }
       return parent[v] = find(parent[v]);
    }


void unite(int v, int u) {
    int x=find(v);
    int y=find(u);
    if(x!=y) {
        parent[x]=y;
    }
}

int setCount() {
    int item=0;
    for(int i=0;i<parent.length;i++) {
        if(i==parent[i]) {
            item++;
        }
    }
    return item; // change appropriately 
}

int itemCount() {
    return K;
}

The task which has been assigned to me is to complete properly the following methods :

  1. int find(int v)
  2. void unite(int v,int u)
  3. setCount(int v)

Well,the algorithm seems to be slow and i can't find a suitable solution.



Solution

  • Here are some issues:

    Not a problem, but naming variables as N and K is not helping to make the code readable. Why not give names that actually tell what they are, so you don't need to accompany their definitions with a comment to give that explanation?

    Here is your code with those adaptations:

    public class UnionFind {
        
        private int[] parent;
        private int[] size;
        private int maxItemCount;
        private int numItems;
        private int numSets;
        
        UnionFind(int maxItemCount) {
            this.maxItemCount = maxItemCount;
            numItems = 0;
            numSets = 0;
            parent = new int[maxItemCount];
            size = new int[maxItemCount];
            for (int i = 0; i < maxItemCount; i++) {
                parent[i] = -1;
                size[i] = 0;
            }
        }
        
        void makeSet(int v) {
            if (parent[v] != -1) return; // item v already belongs in a set
            parent[v] = v;
            size[v] = 1;
            numItems++;
            numSets++;  // Keep track of number of sets
        }
        
        int find(int v) {
            if (v == parent[v]) {
                return v;
            }
            return parent[v] = find(parent[v]);
        }
        
        void unite(int v, int u) {
            int x = find(v);
            int y = find(u);
            if (x != y) {
                numSets--; // A union decreases the set count
                // Determine which node becomes the root
                if (size[x] < size[y]) {
                    parent[x] = y;
                    size[y] += size[x]; // Adapt size
                } else {
                    parent[y] = x;
                    size[x] += size[y]; // Adapt size
                }
            }
        }
        
        int setCount() {
            return numSets; // Kept track of it
        }
        
        int itemCount() {
            return numItems;
        }
    }