Disjoint Set - Implemented Using Arrays

 Click Me


What is a Disjoint Set?
  • Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.
  • The disjoint set has mainly 3 Operations:
    • makeset() -> makes 'n' number of disjoint sets containing single elements
    • find(currentSet) -> returns the representative/parent of currentSet
    • union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set. 
  • Before going through code, I would recommend watching this video - https://www.youtube.com/watch?v=wU6udHRIkcc

Code:


public class Main {
// here 'set' array will store following information about our disjoint set:
// 1. index of set denotes the nodes
    // For example - index 0 denotes node1, index 4 denotes node 4 and so on.
// 2. If there is a negative value at a index, then it indicates that node denoted by that particular index is a parent node
// For example - suppose index 0 has value -1 in the array 'set', so this indicates that node denoted by the index 0 is a parent node.
// 3. If there is a negative value at a index, then it's absolute value indicates about the number of nodes under that parent.
// For example - suppose index 1 has value -2, so this indicates that node represented by index 1 is a parent and has 2 nodes(including itself) under it.
    int[] set;
    
    // Constructor
    Main(int size){
        this.set = new int[size];
    }
    
    // method to make 'size' number of disjoint sets initially
    public void makeSet(int size){
        for(int i=0;i<size;i++){
            this.set[i]=-1;
        }
    }
    
    // method to find the disjoint set to which x belongs
    // find using path compression
    public int find(int x){
        int parent = this.set[x];
        if(parent<0){
            parent =  x;
        }
        else{
            parent = find(parent);
        }
        
        return parent;
    }
    
    // x and y are index/nodes
    // method to union the disjoint sets of elements x and y if they belong to different disjoint sets
    public void union(int x,int y){
        int parentX = find(x);
        int parentY = find(y);
        
        // already belong to same set
        if(parentX==parentY){
        System.out.println();
            System.out.println(x+" and "+y+" already belongs to the same set");
            return;
        }
        
        // Not belong to the same set
        // we need to decide which set is to be merged where
        
        // Calculating weight/rank of x and y nodes
        // weight node tells us how many nodes/elements are associated with the disjoint set of current element
        // these should always come negative as it is indicating the parent
        int weightX = this.set[parentX];
        int weightY = this.set[parentY];
        
        
        // if weight/rank is equal, merging y into x
        if(Math.abs(weightX)==Math.abs(weightY)){
            this.set[parentY] = parentX;
            // As we are merging Y into X, the weight of X will be updated.
            // if weight of Y is negative, we take it's weight's absolute value and add it to current weight of X
            weightX = -1 * (Math.abs(weightX)+ ((weightY<0) ? Math.abs(weightY) : 1));
            
            this.set[parentX] = weightX;
        }
        // if weight/rank of X is greater than Y, merge Y into X
         else if(Math.abs(weightX) > Math.abs(weightY)) {
        this.set[parentY] = parentX;
             
             weightX = -1 * (Math.abs(weightX)+ ((weightY<0) ? Math.abs(weightY) : 1));
             
             this.set[parentX] = weightX;
         }
        // if weight/rank of Y is greater than X, merge X into Y
         else if(Math.abs(weightX) < Math.abs(weightY)) {
        this.set[parentX] = parentY;
             
             weightY = -1 * (Math.abs(weightY)+ ((weightX<0) ? Math.abs(weightX) : 1));
             
             this.set[parentY] = weightY;
         }
 
    }
    
    public static void main(String[] args) throws Exception {
        int size = 8; // for nodes 0,1,2,3,4,5,6,7
        
        Main disjointSet = new Main(size);
        
        disjointSet.makeSet(size);
        
         for(int i=0;i<size;i++){
             System.out.print(disjointSet.find(i)+" ");
         }
        
         disjointSet.union(0, 1);
         disjointSet.union(2, 3);
         disjointSet.union(4, 5);
         disjointSet.union(6, 7);
         
         disjointSet.union(1, 3);
         disjointSet.union(1, 4);
         disjointSet.union(0, 2);
         disjointSet.union(5, 7);
         disjointSet.union(4, 6);
         
         System.out.println();
         for(int i=0;i<size;i++){
             System.out.print(disjointSet.find(i)+" ");
         }
         
    }
}


Output:

0 1 2 3 4 5 6 7 
0 and 2 already belongs to the same set

4 and 6 already belongs to the same set

0 0 0 0 0 0 0 0


Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more