WikiGalaxy
Applications of Disjoint Set
Network Connectivity
Disjoint sets are used to determine if two nodes belong to the same component in a network, which is essential for network connectivity problems. This helps in efficiently managing and querying connected components in a network graph.
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]);
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}
}
Cycle Detection
Disjoint set data structures can be used to detect cycles in an undirected graph efficiently. By using union and find operations, it is possible to check if adding an edge will form a cycle.
class Graph {
int V, E;
Edge[] edge;
class Edge {
int src, dest;
}
public Graph(int v, int e) {
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void union(int parent[], int x, int y) {
parent[x] = y;
}
boolean isCycle(Graph graph) {
int[] parent = new int[graph.V];
Arrays.fill(parent, -1);
for (int i = 0; i < graph.E; ++i) {
int x = find(parent, graph.edge[i].src);
int y = find(parent, graph.edge[i].dest);
if (x == y)
return true;
union(parent, x, y);
}
return false;
}
}
Kruskal's Minimum Spanning Tree
Kruskal's algorithm uses disjoint set data structures to find a minimum spanning tree for a connected weighted graph. It repeatedly adds the next lightest edge that does not form a cycle.
class KruskalMST {
class Edge implements Comparable {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
};
class Subset {
int parent, rank;
};
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();
}
int find(Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void union(Subset subsets[], int x, int y) {
int rootX = find(subsets, x);
int rootY = find(subsets, y);
if (subsets[rootX].rank < subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}
void KruskalMST() {
Edge[] result = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
Subset[] subsets = new Subset[V];
for (i = 0; i < V; ++i)
subsets[i] = new Subset();
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(subsets, x, y);
}
}
}
}
Image Segmentation
In computer vision, disjoint sets can be used for image segmentation tasks. They help in grouping pixels into segments, which are then used to identify objects or regions within an image.
// Pseudocode for Image Segmentation using Disjoint Set
class ImageSegmentation {
int[] parent;
int[] rank;
public ImageSegmentation(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[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public void segmentImage(int[][] image) {
// Implement segmentation logic using union-find
}
}
Social Network Analysis
Disjoint sets can be used in social network analysis to identify communities or groups within a network. This helps in understanding the structure and dynamics of social interactions.
// Pseudocode for Social Network Analysis using Disjoint Set
class SocialNetwork {
int[] parent;
public SocialNetwork(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]);
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}
public void analyzeNetwork(int[][] connections) {
// Implement community detection using union-find
}
}
