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.

```
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

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

« Prev - Java Program to Implement Threaded Binary Tree

» Next - Java Program to Implement Bloom Filter

Related Posts:

Recommended Articles: