WikiGalaxy
Path Compression in Disjoint Set ADT
Example 1: Basic Path Compression
Understanding Path Compression
Path compression is a technique used in the disjoint set data structure to flatten the structure of the tree whenever Find is called on it. This ensures that each node points directly to the root, leading to an amortized time complexity of nearly constant time for each operation.
class DisjointSet {
int[] parent;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
}
Efficiency Improvement
The path compression technique drastically reduces the time complexity of union-find operations, making them almost constant time.
Example 2: Union Operation with Path Compression
Combining Sets
The union operation combines two sets into one. With path compression, the trees representing sets become shallower, which speeds up future operations.
class DisjointSet {
int[] parent, rank;
public DisjointSet(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
Rank Optimization
Using ranks helps keep the tree as flat as possible, further optimizing the union operation.
Example 3: Path Compression in Graph Connectivity
Graph Connectivity
Path compression can be used to determine connectivity in a graph efficiently. Each connected component of the graph is represented as a disjoint set.
class Graph {
DisjointSet ds;
public Graph(int n) {
ds = new DisjointSet(n);
}
public void addEdge(int u, int v) {
ds.union(u, v);
}
public boolean isConnected(int u, int v) {
return ds.find(u) == ds.find(v);
}
}
Application in Graphs
This method is particularly useful in applications such as Kruskal's algorithm for finding the minimum spanning tree.
Example 4: Cycle Detection in Graphs
Cycle Detection
Path compression can also be used to detect cycles in an undirected graph by checking if two vertices belong to the same set.
class CycleDetection {
DisjointSet ds;
public CycleDetection(int n) {
ds = new DisjointSet(n);
}
public boolean addEdge(int u, int v) {
int rootU = ds.find(u);
int rootV = ds.find(v);
if (rootU == rootV) {
return true; // Cycle detected
}
ds.union(u, v);
return false;
}
}
Cycle Detection Efficiency
Using path compression, cycle detection can be performed efficiently, making it suitable for large graphs.
Example 5: Dynamic Connectivity Problem
Dynamic Connectivity
The dynamic connectivity problem involves determining if two elements are in the same connected component dynamically as edges are added.
class DynamicConnectivity {
DisjointSet ds;
public DynamicConnectivity(int n) {
ds = new DisjointSet(n);
}
public void connect(int u, int v) {
ds.union(u, v);
}
public boolean isConnected(int u, int v) {
return ds.find(u) == ds.find(v);
}
}
Real-time Connectivity Check
With path compression, connectivity checks can be performed in real-time, allowing for efficient updates and queries.
