Java Program to Implement Disjoint Set Data Structure

This Java program is to Implement Disjoint set data structure. In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.

Here is the source code of the Java program to implement disjoint data structure. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.HashSet;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Set;
  7.  
  8. public class DisjointSets 
  9. {
  10.     private List<Map<Integer, Set<Integer>>> disjointSet;
  11.  
  12.     public DisjointSets()
  13.     {
  14.         disjointSet = new ArrayList<Map<Integer, Set<Integer>>>();
  15.     }
  16.  
  17.     public void create_set(int element)
  18.     {
  19.         Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
  20.         Set<Integer> set = new HashSet<Integer>();
  21.         set.add(element);
  22.         map.put(element, set);
  23.         disjointSet.add(map);
  24.     }
  25.  
  26.     public void union(int first, int second)
  27.     {
  28.         int first_rep = find_set(first);
  29.         int second_rep = find_set(second);
  30.  
  31.         Set<Integer> first_set = null;
  32.         Set<Integer> second_set = null;
  33.  
  34.         for (int index = 0; index < disjointSet.size(); index++)
  35.         {
  36.             Map<Integer, Set<Integer>> map = disjointSet.get(index);
  37.             if (map.containsKey(first_rep))
  38.             {
  39.                 first_set = map.get(first_rep);
  40.             } else if (map.containsKey(second_rep))
  41.             { 
  42.                 second_set = map.get(second_rep);
  43.             }
  44.         }
  45.  
  46.         if (first_set != null && second_set != null)
  47.         first_set.addAll(second_set);
  48.  
  49.         for (int index = 0; index < disjointSet.size(); index++)
  50.         {
  51.             Map<Integer, Set<Integer>> map = disjointSet.get(index);
  52.             if (map.containsKey(first_rep))
  53.             {
  54.                 map.put(first_rep, first_set);
  55.             } else if (map.containsKey(second_rep))
  56.             {
  57.                 map.remove(second_rep);
  58.                 disjointSet.remove(index);
  59.             }
  60.         }
  61.  
  62.         return;
  63.     }
  64.  
  65.     public int find_set(int element)
  66.     {
  67.         for (int index = 0; index < disjointSet.size(); index++)
  68.         {
  69.             Map<Integer, Set<Integer>> map = disjointSet.get(index);
  70.             Set<Integer> keySet = map.keySet();
  71.             for (Integer key : keySet)
  72.             {
  73.                 Set<Integer> set = map.get(key);
  74.                 if (set.contains(element))
  75.                 {
  76.                     return key;
  77.                 }
  78.             }
  79.         }
  80.         return -1;
  81.     }
  82.  
  83.     public int getNumberofDisjointSets()
  84.     {
  85.         return disjointSet.size();
  86.     }
  87.  
  88.     public static void main(String... arg)
  89.     {
  90.         DisjointSets disjointSet = new DisjointSets();
  91.  
  92.         for (int i = 1; i <= 5; i++)
  93.         {
  94.             disjointSet.create_set(i);
  95.         }
  96.  
  97.         System.out.println("ELEMENT : REPRESENTATIVE KEY");
  98.         for (int i = 1; i <= 5; i++)
  99.         {
  100.             System.out.println(i + "\t:\t" + disjointSet.find_set(i));
  101.         } 
  102.  
  103.         disjointSet.union(1, 5);
  104.         disjointSet.union(5, 3);
  105.  
  106.         System.out.println("\nThe Representative keys after performing the union operation\n");
  107.         System.out.println("Union of (1 and 5)  and (5 and 3) ");
  108.  
  109.         System.out.println("ELEMENT : REPRESENTATIVE KEY");
  110.         for (int i = 1; i <= 5; i++)
  111.         {
  112.             System.out.println(i + "\t:\t" + disjointSet.find_set(i));
  113.         }
  114.  
  115.         System.out.println("\nThe number of disjoint set : "+ disjointSet.getNumberofDisjointSets());
  116.     }
  117. }


$javac DisjointSets.java
$java DisjointSets
 
ELEMENT : REPRESENTATIVE KEY
1	:	1
2	:	2
3	:	3
4	:	4
5	:	5
 
The Representative keys after performing the union operation
 
Union of (1 and 5)  and (5 and 3) 
ELEMENT : REPRESENTATIVE KEY
1	:	1
2	:	2
3	:	1
4	:	4
5	:	1
 
The number of disjoint set : 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.