Disjoint-Set Data Structure UNION-FIND

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) 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.

Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn’t contain any self-loops.

We can keeps track of the subsets in a 1D array, lets call it parent[].

Applications:

Detect Cycle in a an Undirected Graph 

Minium Spanning Tree - Kruskals

The implementation of union() and find() is naive and takes O(n) time in worst case. 
These methods can be improved to O(Logn) using Union by Rank or Height - Next post.

Union-Find in O(n) :

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

package g4g.Graph;/** * Created by seesunda on 12/6/2014. */ import java.io.InputStreamReader; import java.io.IOException; import java.io.BufferedReader; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.StringTokenizer; import java.io.InputStream; class UFinN { int V; int E; Edge[] edges; UFinN(int v, int e) { this.V = v; this.E = e; this.edges = new Edge[e]; for(int i=0;i<e;i++) edges[i] = new Edge(); } class Edge { int src; int dest; } public static void main(String[] args) { UFinN u = new UFinN(3,3); // add edge 0-1 u.edges[0].src = 0; u.edges[0].dest = 1; // add edge 1-2 u.edges[1].src = 1; u.edges[1].dest = 2; // add edge 0-2 u.edges[2].src = 0; u.edges[2].dest = 2; if(hasCycle(u)) System.out.println("Detected Cycle"); else System.out.println("No Cycle"); } public static boolean hasCycle(UFinN u) { int[] parent = new int[u.V]; Arrays.fill(parent, -1); for(int i=0;i<u.E;i++) { int x = find(parent,u.edges[i].src); int y = find(parent,u.edges[i].dest); //Belongs to same set if(x == y) { return true; } union(parent,x,y); } return false; } public static int find(int[] parent,int vertex) { while(parent[vertex] != -1) vertex = parent[vertex]; return vertex; } public static void union(int[] parent,int x,int y) { int xset = find(parent,x); int yset = find(parent,y); parent[xset] = yset; } }