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 Check Whether an Undirected Graph Contains a Eulerian Path
Java Program to Implement Stack using Linked List
Call Methods at Runtime Using Java Reflection
Programmatic Transaction Management in Spring
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Java Program to Implement SimpeBindings API
Java Map With Case-Insensitive Keys
Java Program to Implement Interval Tree
Working with Kotlin and JPA
Convert String to Byte Array and Reverse in Java
Working With Maps Using Streams
Spring WebClient vs. RestTemplate
Java Program to Implement Doubly Linked List
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Implement LinkedBlockingDeque API
Spring Boot - Service Components
Send an email with an attachment
Java Program to Perform Finite State Automaton based Search
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Java Program to Perform Searching Using Self-Organizing Lists
Spring Security Basic Authentication
The StackOverflowError in Java
Java Program to Implement ArrayBlockingQueue API
Reactive WebSockets with Spring 5
The Java 8 Stream API Tutorial
Check if there is mail waiting
Java Program to Implement ScapeGoat Tree
Spring Data MongoDB – Indexes, Annotations and Converters
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Apache Commons Collections SetUtils
Java – InputStream to Reader
Easy Ways to Write a Java InputStream to an OutputStream