Cycle in undirected graph using disjoint set

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.

Disjoint set data structure

Disjoint set data structure

A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, β‹― , 𝑆𝑛 } of disjoint dynamic sets. Subsets are said to be disjoint if intersection between them is NULL. For example, set {1,2,3} and {4,5,6} are disjoint sets, but {1,2,3} and {1,3,5} are not as intersection is {1,3} which is not null. Another important thing about the disjoint set is that every set is represented by a member of that set called as representative.

Operations on this disjoint set data structure:
1. Make Set:Β Creates a new set with one element x, since the sets are disjoint, we require that x not already be in any of the existing sets.
2. Union: Merges two sets containing x and y let’s say Sx and Sy and destroys the original sets.
3.Find: Returns the representative of the set which element belongs to.

Let’s take an example and see how disjointed sets can be used to find the connected components of an undirected graph.

To start with, we will make a set for each vertex by using make-set operation.

for each vertex v in G(V)
    do makeSet(v)

Next process all the edges in the graph (u,v) and connect set(u) and set(v) if the representatives of the set which contains u and set which contains v are not same.

for each edge (u,v) in 𝐺(E)
    do if findSet(u) != findSet(v)
        then union(u, v)

Once above preprocessing steps have run, then we can easily find answer if two vertices u and v are part of same connected component or not?

boolean isSameComponent(u, v)
 if findSet(u)==findSet(v)
     return True
 else 
     return False

To find how many components are there, we can look at how many disjoint sets are there and that will give us the number of connected components in a graph. Let’s take an example and see how it works.

disjoint set data structure

Below table shows the processing of each edge in the graph show figure above.

disjoint sets

Now, how can we implement sets and quickly do union and find operations? There are two ways to do it.

Disjoint set representation using an array

Simple implementation of disjoint set is using an array which maintains their representative of element i in A[i]. To this implementation to work, it is must that all the element in the set are in range 0 to N-1 where N is size of the array.

Initially, in makeSet() operation, set A[i]=i, for each i between 0 and N-1 and create the initial versions of the sets.

disjoint set data structure representation of graph

for (int i=0; i<N; i++) A[i] = i;

Union operation for the sets that contain integers u and v, we scan the array A and change all the elements
that have the value A[u] to have the value A[v]. For example, we if want to connect an edge between 1 and 2 in the above set, the union operation will replace A[2] with A[1].

disjoint set data structure time complexity and implementation in java

Now, if want to add an edge between 3 and 1. In this case, u = 3 and v = 1. A[3] = 3 and A[1] = 1. So, we will replace all the indices of A where A[i] = 1. So final array looks like this.

disjoint set data structure java

Similarly, if want to add an edge from 6 to 7.
disjoint sets

//change all elements from A[u] to A[v].
void union(int A[], int u, int v){
    int temp = A[u];
    for(int i=0; i<A.length; i++){
        if(A[i] == temp)
            A[i] = A[v]; 
    }
}

findSet(v) operation returns the value of A[v].

int findSet(int A[], int v){
    return A[v]
}

The complexity of makeSet() operation is O(n) as it initializes the entire array. Union operation take every time O(n) operations if we have to connect n nodes, then it will be O(n2) operations. FindSet() operation has constant time complexity.

We can represent a disjoint set using linked list too. In that case, each set will be a linked list, and head of the linked list will be the representative element. Each node contains two pointers, one to its next element it the set and other points to the representative of the set.

To initialize, each element will be added to a linked list. To union (u, v), we add the linked list which contains u to end of the linked list which contains v and change representation pointer of each node to point to the representation of list which contained v.

The complexity of union operation is again O(n). Also, find operation can be O(1) as it returns the representative of it.

Disjoint set forest

The disjoint-forests data structure is implemented by changing the interpretation of the meaning of the element of array A. Now each A[i] represents an element of a set and points to another element of that set. The root element points to itself. In short, A[i] now points to the parent of i.

Makeset operation does not change, as to start with each element will be the parent of itself.
Union operation will change, if we want to connect u and v with an edge, we update A[root of u] with the root of v. How to find the root of an element? As we have the relationship that A[i] is the parent of i, we can move up the chain until we find a case where A[i] == i, that case, i is the root of v.

//finding root of an element
int root(int A[],int i){
    while(A[i] != i){
        i = A[i];
    }
    return i;
}

/*Changed union function where we connect 
  the elements by changing the root of 
  one of the elements
*/

int union(int A[] ,int u ,int v){
    int rootU = root(A, u);       
    int rootV = root(A, v);  
    A[rootU] = rootV ; 
}

This implementation has a worst-case complexity of O(n) for union function. And also we made the worst complexity of findSet operation as O(n).

However, we can do some ranking on the size of trees which are being connected. We make sure that always root of smaller tree point to the root of the bigger tree.

void union(int[] A, int[] sz, u, v){

    //Finding roots
    for (int i = u; i != A[i]; i = A[i]) ;
    for (int j = v; j != A[j]; j = A[j]) ;

    if (i == j) return;
    //Comparing size of tree to put smaller tree root under 
    // bigger tree's root.
    if (sz[i] < sz[j]){
        A[i] = j;
        sz[j] += sz[i];
    }
    else {
        A[j] = i; 
        sz[i] += sz[j];
    }
}

In the next few posts, we will be discussing applications of this method to solve different problems on graphs.
Please share if there is something wrong or missing. If you are preparing for an interview, and want coaching sessions to prepare for it, please signup for free demo session.