×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Find disjoint sets in a graph using disjoint set ADT operations FIND, UNION

In this article, we are going to see usage of disjoint set ADT operation to find disjoint sets in a graph.
Submitted by Radib Kar, on September 11, 2020

Prerequisite: ADT set

Let us first discuss what disjoint sets in a graph is? Disjoint sets in a graph mean components of a graph. Each connected component is treated as a disjoint set since it has no relation with the other components. Each connection (edge) is said to be the relation between two nodes. Two nodes having a relation falls in the same set.

In the below input graph,

Find disjoint sets in a graph (1)

We have two components and thus two disjoint sets. Those are,

Find disjoint sets in a graph (2)

Now, how we can find the disjoint sets. Here comes the find(X) & UNION (X,Y) ADT operation.

The operation finds the set name and here we use array for that. We use a parent array to store all set names initially. Initially all are themselves (i for node i).

We call it a parent array to store the set names:

Find disjoint sets in a graph (0)

The algorithm is:

For each edge in the edge list:

If the nodes on the edge are in same set, do nothing, otherwise, we will UNION them as they have relations between them and should come under same set.

To check whether the two nodes are in same set we use FIND

Implementation of FIND & UNION

1) FIND(X)

We use a recursive function find (X, parent []) to find the set name of element X.

The implementation is like below:

FUNCTION find(int X, int parent[]):
    If(parent[x]==X)
        return X;
    return find(parent[x], parent)
End FUNCTION 

2) UNION (X, Y)

Union means we bring both elements under same set which is as simple assigning X as parent of Y

parent[Y]=X

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

//FIND(X)
int find(int X, vector<int>& parent)
{
    if (parent[X] == X)
        return X;

    return find(parent[X], parent);
}

//UNION(X,Y)
void UNION(int X, int Y, vector<int>& parent)
{
    parent[Y] = X;
}

int main()
{
    int n, m;
 
    cout << "Enter number of edges\n";
    cin >> n;
    cout << "Enter number of nodes\n";
    cin >> m;
 
    //edges list
    //each edge is a vector [u,v]
    vector<vector<int> > edges(n);
 
    for (int i = 0; i < n; i++) {
        int u, v;
        cout << "info for edge " << i + 1 << endl;
        cout << "Enter source node u: ";
        cin >> u;
        cout << "Enter destination node v: ";
        cin >> v;
        edges[i] = vector<int>{ u, v };
    }

    vector<int> parent(m + 1);
 
    for (int i = 1; i <= m; i++)
        parent[i] = i;

    for (auto edge : edges) {
        //find set name for source node, u
        int x = find(edge[0], parent);
        //cout<<x<<endl;
        //find set name for destination node, v
        int y = find(edge[1], parent);
        //cout<<y<<endl;
        //if they are not in same set already, do their union
        if (x != y) {
            UNION(x, y, parent);
        }
    }

    //number of disjoint set is number of -1 in the parent set
    int count = 0;
    for (int i = 1; i <= m; i++)
        if (parent[i] == i)
            count++;
    cout << "Number of disjoint set is :" << count << endl;

    cout << "printing the parent array now:\n";
    for (int i = 1; i <= m; i++)
        cout << parent[i] << " ";
    cout << endl;

    return 0;
}

Output:

Enter number of edges
6
Enter number of nodes
8
info for edge 1
Enter source node u: 1
Enter destination node v: 2
info for edge 2
Enter source node u: 1
Enter destination node v: 3
info for edge 3
Enter source node u: 2
Enter destination node v: 4
info for edge 4
Enter source node u: 2
Enter destination node v: 5
info for edge 5
Enter source node u: 6
Enter destination node v: 7
info for edge 6
Enter source node u: 7
Enter destination node v: 8
Numebr of disjoint set is :2
printing the parent array now:
1 1 1 1 1 6 6 6 

Dry Run for the example:

So the edge list is:

[ [1, 2],

  [1, 3],

  [2, 4],

  [2, 5],

  [6, 7],

  [7, 8] ]

We will process each edge one by one and do necessary FIND & UNION

Initially parent[] is:

Find disjoint sets in a graph (a)

Edge 1:

So source is 1 and destination is 2

We will find parent of both 1 & 2

Finding parent of 1

parent[1] is 1 so it returns 1

Finding parent of 2

parent[2] is 2 so it returns 2

Since both their set names( parent) are different we do a union

Thus parent[2]=1 now, so after processing edge 1

Find disjoint sets in a graph (b)

Edge 2:

So source is 1 and destination is 3

We will find parent of both 1 & 3

Finding parent of 1

parent[1] is 1 so it returns 1

Finding parent of 3

parent[3] is 3 so it returns 3 

Since both their set names( parent) are different we do a union

Thus parent[3]=1 now, so after processing edge 2

Find disjoint sets in a graph (c)

Find disjoint sets in a graph (3)

Edge 3:

So source is 2 and destination is 4

We will find parent of both 2 & 4

Finding parent of 2

parent[2] is 1 so it returns find(1, parent) and that returns 1 ultimately (parent[1]== 1)

Finding parent of 4

parent[4] is 4 so it returns 4

Since both their set names( parent) are different we do a union

Thus parent[4]=1 now, so after processing edge 3

Find disjoint sets in a graph (d)

Find disjoint sets in a graph (4)

Edge 4:

So source is 2 and destination is 5

We will find parent of both 2 & 5

Finding parent of 2

parent[2] is 1 so it returns find(1, parent) and that returns 1 ultimately (parent[1]== 1)

Finding parent of 5

parent[5] is 5 so it returns 5

Since both their set names( parent) are different we do a union

Thus parent[5]=1 now, so after processing edge 4

Find disjoint sets in a graph (e)

Find disjoint sets in a graph (5)

Edge 5:

So source is 6 and destination is 7

We will find parent of both 6 & 7

Finding parent of 6

parent[6] is 6 so it returns 6

Finding parent of 7

parent[7] is 7 so it returns 7

Since both their set names( parent) are different we do a union

Thus parent[7]=6 now, so after processing edge 5

Find disjoint sets in a graph (f)

Find disjoint sets in a graph (6)

Edge 6:

So source is 7 and destination is 8

We will find parent of both 7 & 8

Finding parent of 7

parent[7] is 6 so it returns find(6, parents) which ultimately returns 6

Finding parent of 8

parent[8] is 8 and thus it returns 8

Since both their set names( parent) are different we do a union

Thus parent[8]=6 now, so after processing edge 6

Find disjoint sets in a graph (g)

Find disjoint sets in a graph (7)

So, the final parent array is:

Find disjoint sets in a graph (h)

Hence there are two disjoint sets with parents 1 & 6.

All nodes having same parent fall into same set. So the sets are: [1, 2, 3,4 5] & [6, 7, 8]



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.