The Disjoint Set Abstract Data Type (ADT) is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. It is particularly useful in graph algorithms, such as Kruskal's Minimum Spanning Tree algorithm and network connectivity problems.

Union-Find Operations

The two primary operations in a Disjoint Set ADT are Find, which determines the set a particular element belongs to, and Union, which merges two sets into a single set.


class DisjointSet {
    private int[] parent;
    private int[] rank;

    public DisjointSet(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    public void union(int root1, int root2) {
        int rootA = find(root1);
        int rootB = find(root2);
        if (rootA != rootB) {
            if (rank[rootA] < rank[rootB]) {
                parent[rootA] = rootB;
            } else if (rank[rootA] > rank[rootB]) {
                parent[rootB] = rootA;
            } else {
                parent[rootB] = rootA;
                rank[rootA]++;
            }
        }
    }
}

Path Compression

Path compression is a technique used in the Find operation to make the tree flat, which helps in speeding up future operations by reducing the path length to the root.

Union by Rank

Union by rank is a technique used in the Union operation to ensure that the smaller tree is always added under the root of the larger tree, thus keeping the tree shallow.

Console Output:

Union-Find operations executed successfully.

Example: Kruskal's Algorithm

Using Disjoint Set in Kruskal's Algorithm

Kruskal's algorithm is a minimum spanning tree algorithm that uses the Disjoint Set ADT to efficiently determine whether adding an edge would create a cycle.


class KruskalMST {
    class Edge implements Comparable {
        int src, dest, weight;
        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    };

    int V, E;
    Edge[] edge;

    KruskalMST(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    void Kruskal() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);

        DisjointSet ds = new DisjointSet(V);

        i = 0;
        while (e < V - 1) {
            Edge next_edge = edge[i++];
            int x = ds.find(next_edge.src);
            int y = ds.find(next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                ds.union(x, y);
            }
        }
    }
}

Cycle Detection

In Kruskal's algorithm, the Disjoint Set ADT helps in detecting cycles efficiently, ensuring that only the edges that do not form a cycle are added to the MST.

Console Output:

Minimum Spanning Tree constructed successfully.

Example: Network Connectivity

Checking Network Connectivity

The Disjoint Set ADT can be used to determine if there is a path between any two nodes in a network, which is crucial for network reliability and redundancy checks.


public class NetworkConnectivity {
    public static boolean isConnected(int[][] connections, int n) {
        DisjointSet ds = new DisjointSet(n);
        for (int[] connection : connections) {
            ds.union(connection[0], connection[1]);
        }
        int root = ds.find(0);
        for (int i = 1; i < n; i++) {
            if (ds.find(i) != root) {
                return false;
            }
        }
        return true;
    }
}

Network Partitioning

By using the Disjoint Set ADT, it's possible to quickly determine if a network is partitioned into multiple isolated sub-networks, which could indicate a failure or need for additional links.

Console Output:

The network is fully connected.

Example: Dynamic Connectivity

Handling Dynamic Changes

Dynamic connectivity problems involve determining the connectivity between nodes in a network that can change dynamically, i.e., edges can be added or removed.


public class DynamicConnectivity {
    private DisjointSet ds;

    public DynamicConnectivity(int n) {
        ds = new DisjointSet(n);
    }

    public void addConnection(int u, int v) {
        ds.union(u, v);
    }

    public boolean isConnected(int u, int v) {
        return ds.find(u) == ds.find(v);
    }
}

Real-Time Network Updates

The Disjoint Set ADT allows for efficient updates and queries in real-time scenarios, making it ideal for applications like social networks and online games where connections change frequently.

Console Output:

Connection status updated.

Example: Image Processing

Connected Component Labeling

In image processing, the Disjoint Set ADT can be used for connected component labeling, which involves identifying and labeling connected regions in binary images.


public class ImageProcessing {
    public int[][] labelComponents(int[][] binaryImage) {
        int rows = binaryImage.length;
        int cols = binaryImage[0].length;
        DisjointSet ds = new DisjointSet(rows * cols);

        // Example logic for labeling components
        // This would involve iterating over the image and applying union-find

        return new int[rows][cols]; // Placeholder for labeled image
    }
}

Efficient Image Analysis

By utilizing the Disjoint Set ADT, connected component labeling can be performed efficiently, which is essential for tasks like object detection and image segmentation.

Console Output:

Image components labeled successfully.