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.
import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; public class DisjointSets { private List<Map<Integer, Set<Integer>>> disjointSet; public DisjointSets() { disjointSet = new ArrayList<Map<Integer, Set<Integer>>>(); } public void create_set(int element) { Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>(); Set<Integer> set = new HashSet<Integer>(); set.add(element); map.put(element, set); disjointSet.add(map); } public void union(int first, int second) { int first_rep = find_set(first); int second_rep = find_set(second); Set<Integer> first_set = null; Set<Integer> second_set = null; for (int index = 0; index < disjointSet.size(); index++) { Map<Integer, Set<Integer>> map = disjointSet.get(index); if (map.containsKey(first_rep)) { first_set = map.get(first_rep); } else if (map.containsKey(second_rep)) { second_set = map.get(second_rep); } } if (first_set != null && second_set != null) first_set.addAll(second_set); for (int index = 0; index < disjointSet.size(); index++) { Map<Integer, Set<Integer>> map = disjointSet.get(index); if (map.containsKey(first_rep)) { map.put(first_rep, first_set); } else if (map.containsKey(second_rep)) { map.remove(second_rep); disjointSet.remove(index); } } return; } public int find_set(int element) { for (int index = 0; index < disjointSet.size(); index++) { Map<Integer, Set<Integer>> map = disjointSet.get(index); Set<Integer> keySet = map.keySet(); for (Integer key : keySet) { Set<Integer> set = map.get(key); if (set.contains(element)) { return key; } } } return -1; } public int getNumberofDisjointSets() { return disjointSet.size(); } public static void main(String... arg) { DisjointSets disjointSet = new DisjointSets(); for (int i = 1; i <= 5; i++) { disjointSet.create_set(i); } System.out.println("ELEMENT : REPRESENTATIVE KEY"); for (int i = 1; i <= 5; i++) { System.out.println(i + "\t:\t" + disjointSet.find_set(i)); } disjointSet.union(1, 5); disjointSet.union(5, 3); System.out.println("\nThe Representative keys after performing the union operation\n"); System.out.println("Union of (1 and 5) and (5 and 3) "); System.out.println("ELEMENT : REPRESENTATIVE KEY"); for (int i = 1; i <= 5; i++) { System.out.println(i + "\t:\t" + disjointSet.find_set(i)); } System.out.println("\nThe number of disjoint set : "+ disjointSet.getNumberofDisjointSets()); } }
$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
Related posts:
Java Program to Implement Suffix Array
Spring REST with a Zuul Proxy
Guide to the Java Queue Interface
Returning Image/Media Data with Spring MVC
Java Program to Implement Expression Tree
JUnit5 @RunWith
Constructor Injection in Spring with Lombok
Guide to java.util.concurrent.Future
Spring Boot - Google OAuth2 Sign-In
Java Program to Implement Stack
Logout in an OAuth Secured Application
Java Program to Perform Complex Number Multiplication
ArrayList trong java
Prevent Cross-Site Scripting (XSS) in a Spring Application
Java Program to Check whether Graph is Biconnected
Java Program to Implement the Vigenere Cypher
Difference Between Wait and Sleep in Java
Batch Processing with Spring Cloud Data Flow
Guide to Guava Table
Stack Data Structure
Quick Guide to the Java StringTokenizer
Concurrent Test Execution in Spring 5
Spring Boot - File Handling
Comparing Long Values in Java
So sánh ArrayList và Vector trong Java
Request Method Not Supported (405) in Spring
Spring RequestMapping
Java Program to Implement Variable length array
Spring Boot - Bootstrapping
Cachable Static Assets with Spring MVC
Guide to WeakHashMap in Java
Java Program to Implement Stack using Two Queues