Detect Cycle in a an Undirected Graph in Java

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[].

Program Sample:

/**
 *
 */
/**
 * @author Abhinaw.Tripathi
 *
 */
public class Graph
{
int V;

int E;

Edge edge[];
class Edge
{
 int src,dest;
};

public Graph(int v,int e)
{
this.E=e;
this.V=v;
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)
{
int xset=find(parent, x);
int yset=find(parent, y);
parent[xset]=yset;
}

int isCycle(Graph graph)
{
int parent[]=new int[ graph.V];

for (int i=0; i<graph.V; ++i)
            parent[i]=-1;

        for (int i = 0; i < graph.E; ++i)
        {
            int x = graph.find(parent, graph.edge[i].src);
            int y = graph.find(parent, graph.edge[i].dest);

            if (x == y)
                return 1;

            graph.union(parent, x, y);
        }
        return 0;
   
}

public static void main(String[] args)
{
int V = 3, E = 3;
        Graph graph = new Graph(V, E);

        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;

        // add edge 1-2
        graph.edge[1].src = 1;
        graph.edge[1].dest = 2;

        // add edge 0-2
        graph.edge[2].src = 0;
        graph.edge[2].dest = 2;

        if (graph.isCycle(graph)==1)
            System.out.println( "graph contains cycle" );
        else
            System.out.println( "graph doesn't contain cycle" );
}

}

Result:

graph contains cycle