Cycle in undirected graph using disjoint set

Tags: , , , ,

Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1.

detect cycle in undirected graph using disjoint set data structure

Disjoint-set data structure has two operations: union and find. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each edge(u,v) in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not?

detect cycle in undirected graph using disjoint set data structure

To start with, we initialize array A with the elements themselves.

detect cycle in a graph

Now, we process each node of the graph one by one. First is edge(1,2). The root of node(1) is 1 and the root of node(2) is 2. Since the roots of two vertices are different, we update the parent of the root of 2 which is A[2] to the root of 1 which is 1.

Next, we process edge(2,3), here root of the node(2) is 1, whereas the root node(3) is 3. Again they differ, hence update A[root of 3] with root 2, i.e A[3] = 1;

Now, process edge(2,4), it will end up with A[4] = 1, can you deduce why? And similarly edge(4,6) will also lead to update A[6] = 1.

detect cycle in directed graph using disjoint sets

Now, we process the edge(6,1). Here, root of node(6) is 1 and also the root of node(1) is 1. Both the nodes have same root, that means there is a cycle in the directed graph.

detect a cycle in undirected graph

To detect a cycle in direct graph : Implementation

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    private boolean isDirected;
    private int count;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        if(!this.G.containsKey(dest)) {
            this.G.put(dest, new ArrayList<>());
        }
        //In case graph is undirected
        if(!this.isDirected) {
                this.G.get(dest).add(start);
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }

    public boolean isCycleWithDisjointSet() {
        int[] parent = new int[this.G.size() + 1];

        for (int u = 1; u < this.G.size() + 1; u++) {
            //Process edge from each node.

            //Find root of u
            int i, j;

            //Worst complexity is O(V)
            for(i=u; i != parent[i]; i = parent[i]);

            /*This loop will run for O(E) times for all 
             the vertices combined. */
            for(int v: this.G.get(u)){
                for(j=v; j != parent[j]; j = parent[j]);

                if(i == j){
                    System.out.println("Cycle detected at 
                                        ("+ u + "," + v + ")");
                    return true;
                }

                parent[i] = j;
            }
        }
        return false;
    }
}

Test cases

package test.Graphs;

import com.company.Graphs.AdjacencyList;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyListTest {
    @Test
    public void detectCycleInDirectedGraphTest() {

        AdjacencyList tester = new AdjacencyList(false);

        tester.addEdge(1,5);
        tester.addEdge(3,4);
        tester.addEdge(2,4);
        tester.addEdge(1,3);
        tester.addEdge(3,5);
        tester.addEdge(5,2);

        assertEquals(true, tester.isEdge(3,4));
        assertEquals(false, tester.isEdge(1,4));

        assertEquals(true, tester.isCycleWithDisjointSet());

    }
}

Complexity of this algorithm is O(EV) where E is number of edges and V is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.