This Java program is to Implement Disjoint Sets. 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 Sets. 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:
Quick Guide to the Java StringTokenizer
Thực thi nhiều tác vụ cùng lúc như thế nào trong Java?
Java Program to Generate Date Between Given Range
Java Program to Implement Radix Sort
Java Program to Implement Word Wrap Problem
Java Collections Interview Questions
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Converting a List to String in Java
Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph
Getting Started with GraphQL and Spring Boot
Java Program to Implement Skip List
String Processing with Apache Commons Lang 3
Constructor Injection in Spring with Lombok
Java Program to Implement Gauss Seidel Method
Spring Boot - Application Properties
What is Thread-Safety and How to Achieve it?
Java Program to Implement Cartesian Tree
Java Program to Implement Lloyd’s Algorithm
The DAO with Spring and Hibernate
ArrayList trong java
So sánh ArrayList và Vector trong Java
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Java Program to Implement Find all Forward Edges in a Graph
Java Program to Implement Knapsack Algorithm
Concurrent Test Execution in Spring 5
Java Program to Generate a Random Subset by Coin Flipping
Java Program to Describe the Representation of Graph using Adjacency List
Java Program to implement Circular Buffer
Form Validation with AngularJS and Spring MVC
Spring Boot - Twilio
Java Program to Represent Graph Using Linked List
Introduction to Spring Cloud Netflix – Eureka