Disjoint Set Union (DSU)
Union-Find, also known as the Disjoint Set Union (DSU), is a data structure that is used to manage a collection of disjoint (non-overlapping) sets. It supports two primary operations:
Find: Determine the set to which a particular element belongs.
Union: Merge two sets into a single set.
The Union-Find data structure is particularly useful in applications such as cycle detection in undirected graphs, Kruskal's Minimum Spanning Tree algorithm, and more.
Union-Find for Cycle Detection in a Graph
To detect cycles in an undirected graph using Union-Find:
If adding an edge between two vertices causes those vertices to be in the same set (i.e., they are already connected), a cycle is detected.
Otherwise, the edge is added, and the two sets (the sets of the two vertices) are merged.
Key Concepts:
Parent Array: Each vertex points to a "parent" vertex, forming a tree structure that represents the connected components (or sets). Initially, each vertex is its own parent (a standalone set).
Union by Rank: A technique to optimize the union operation by attaching the smaller tree under the root of the larger tree.
Path Compression: A technique to optimize the find operation by making nodes point directly to the root of their set, flattening the tree and speeding up future operations.
Steps for Cycle Detection:
Initialize: Create a parent array where each vertex is its own parent (indicating that each vertex is its own set).
For each edge in the graph:
Use the find operation to determine the sets (or parents) of the two vertices the edge connects.
If the two vertices are in the same set (i.e., their parents are the same), a cycle is detected.
Otherwise, use the union operation to merge the two sets.
If no cycle is found after processing all edges, the graph is cycle-free.
Real-World Applications:
Cycle Detection in Networks: Used to detect loops in networking protocols like Ethernet or for detecting cycles in peer-to-peer networks.
MST (Minimum Spanning Tree): In Kruskal’s algorithm, Union-Find is used to avoid cycles while building the MST by adding the smallest edge between two sets of vertices.
Connected Components: Union-Find helps in efficiently grouping vertices into connected components and detecting connectivity between them, useful in computer vision, social network analysis, and clustering algorithms.