Graph – Find Cycle in Undirected Graph using Disjoint Set (Union-Find)

Objective: Given a graph, check if the graph contains a cycle using disjoint set.

Note: Disjoint-set data structure, also called a union–find data structure or merge–find set.

Example:

Earlier in Detect Cycle in Undirected Graph using DFS we discussed about how to find cycle in graph using DFS. In this article we will discuss how to find cycle using disjoint-set.

It is strongly recommended to read “Disjoint-set data structurebefore continue reading this article.

How to find cycle:

  • The makeset operation makes a new set by creating a new element with a parent pointer to itself.
  • Then process each edge of the graph and perform find and Union operations to make subsets using both vertices of the edge.
  • If find operation on both the vertices returns the same parent (means both vertices belongs to the same subset) then cycle is detected.

Lets walk through one example for more understanding, see the animation below:

find-union-1
find-union-2
find-union-3
find-union-4
find-union-5
find-union-6
previous arrow
PlayPause
next arrow

Java Code:

import java.util.ArrayList;
import java.util.LinkedList;
public class DisjointSet {
static class Edge{
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
}
}
static class Graph{
int vertices;
LinkedList<Edge>[] adjList;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices){
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i <vertices ; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination){
Edge edge = new Edge(source, destination);
adjList[source].addFirst(edge);
allEdges.add(edge); //add to total edges
}
public void makeSet(int [] parent){
//Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i <vertices ; i++) {
parent[i] = i;
}
}
public int find(int [] parent, int vertex){
//chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
if(parent[vertex]!=vertex)
return find(parent, parent[vertex]);;
return vertex;
}
public void union(int [] parent, int x, int y){
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
//make x as parent of y
parent[y_set_parent] = x_set_parent;
}
public boolean isCycle(){
//create a parent []
int [] parent = new int[vertices];
//makeset
makeSet(parent);
//iterate through all the edges and keep making the sets
for (int i = 0; i <allEdges.size() ; i++) {
Edge edge = allEdges.get(i);
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
//check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if(x_set==y_set)
return true;
else
union(parent, x_set, y_set);
}
//if here, means cycle was not found
return false;
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1);
graph.addEgde(0, 2);
graph.addEgde(1, 3);
graph.addEgde(3, 4);
graph.addEgde(2, 3);
graph.addEgde(4, 5);
System.out.println("Graph contains cycle: " + graph.isCycle());
}
}


Output:

Graph contains cycle: true

Ref: wiki