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 Perform Preorder Non-Recursive Traversal of a Given Binary Tree
Java Program to Show the Duality Transformation of Line and Point
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Java Program to Implement Threaded Binary Tree
Java Program to Implement Gaussian Elimination Algorithm
The Basics of Java Security
Limiting Query Results with JPA and Spring Data JPA
Serverless Functions with Spring Cloud Function
Spring 5 Functional Bean Registration
Spring Security Form Login
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Using JWT with Spring Security OAuth
Java toString() Method
Test a REST API with Java
Guide to the Java Queue Interface
Guide to Spring 5 WebFlux
Sử dụng CountDownLatch trong Java
Practical Java Examples of the Big O Notation
Apache Commons Collections Bag
Spring Boot - OAuth2 with JWT
Java Program to Check Multiplicability of Two Matrices
Iterating over Enum Values in Java
Introduction to Spring MVC HandlerInterceptor
Spring Boot - Web Socket
Java Program to Implement Floyd Cycle Algorithm
Converting a Stack Trace to a String in Java
Java Program to Implement Range Tree
Removing all Nulls from a List in Java
Java Program to Implement Suffix Array
Registration with Spring Security – Password Encoding
ArrayList trong java