Disjoint-set data structure is very useful data structure which keeps track of collection of items and its set, i.e which item belongs to which set. it is also called union-find data structure.

disjoint set data structure c++Here we can see four sets and its members. a set is a collection of objects. Assume 1,2,3,4,5,6,7,8,9,10,11,12 to be items. In each set the connection between items shows pair wise relation. For example in set 3 the line between 8 to 9 shows relation between 8 and 9, the relation can be interpreted as an edge of a tree. Note that the divided groups of items ( set1,set2,set3,set4) does not overlap. i.e no two or more sets have common item.

Disjoint Set Operations:

  1.   find() – Determine which set an item belongs to.
  2.   union() – Combine or merge two sets into a single set.

A simple array implementation of disjoint-data structure ( union-find algorithm)

unfLet left side tree is set A and right side tree is set B. A = { 1,2,3,5} and B = { 4,0,6}. The set A can be uniquely identified by  1 which is root of  set A and same as set B can be uniquely identified by  4 which is root of  set B. if  we take an array of length ( total number of items ) and initially assigned each element of array to its index value, then this will represents sparse items. now if we assign ith parent’s node to its ith index then we can easily identified which elements belongs to which sets by getting its root node because root node identifies the sets. like below

//find(int i) – Determine which set an item belongs to.
int find_set(int i)
{
      // If i is the parent of itself
       if( i == parent[i])
       return i;
       else
       // Else if i is not the parent of itself
        // Then i is not the representative of its own set,
        // so we recursively call Find on its parent
       return find_set(parent[i]);
}
void unite_set(int i, int j) {
 
    // Find the id (or the root nodes) for the set that includes i
    int u = this.Find(i),
        // And do the same for the set that includes j
        v = this.Find(j);

    parent[u] = parent[v];
}

Alright we have learn disjoint-set data structure simple implementation. Let us use this DS to detect cycle in connected weighted graph.

mstkdisjoint set data structure c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define edge pair<int,int>

class Graph
{
private:
  vector < pair < int, edge > >G;	// graph
    vector < pair < int, edge > >T;	// mst
  int *parent;
  int V;			// number of vertices/nodes in graph
public:
    Graph (int V);
  void AddEdgeAndWeight (int u, int v, int weight);
  int find_set (int i);
  void union_set (int u, int v);
  bool find_cycle ();
};
Graph::Graph (int V)
{
  parent = new int[V];

//i          0 1 2 3 4 5
//parent[i]  0 1 2 3 4 5
  for (int i = 0; i < V; i++)
    parent[i] = i;

  G.clear ();
  T.clear ();
}

void
Graph::AddEdgeAndWeight (int u, int v, int weight)
{
// reset graph and mst
  G.push_back (make_pair (weight, edge (u, v)));
}

int
Graph::find_set (int i)
{
// If i is the parent of itself
  if (i == parent[i])
    return i;
  else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
    return find_set (parent[i]);
}

void
Graph::union_set (int u, int v)
{
  parent[u] = parent[v];
}

bool
Graph::find_cycle ()
{
  int i, uRep, vRep;
  for (i = 0; i < G.size (); i++)
    {
      uRep = find_set (G[i].second.first);
      vRep = find_set (G[i].second.second);
      if (uRep != vRep)
	{
	  union_set (uRep, vRep);
	}
      else if (uRep = vRep)
	{
	  return true;
	  break;
	}
    }
  return false;
}

int
main ()
{
  Graph g (6);
  g.AddEdgeAndWeight (0, 1, 4);
  g.AddEdgeAndWeight (0, 2, 4);
  g.AddEdgeAndWeight (1, 2, 2);
  g.AddEdgeAndWeight (1, 0, 4);
  g.AddEdgeAndWeight (2, 0, 4);
  g.AddEdgeAndWeight (2, 1, 2);
  g.AddEdgeAndWeight (2, 3, 3);
  g.AddEdgeAndWeight (2, 5, 2);
  g.AddEdgeAndWeight (2, 4, 4);
  g.AddEdgeAndWeight (3, 2, 3);
  g.AddEdgeAndWeight (3, 4, 3);
  g.AddEdgeAndWeight (4, 2, 4);
  g.AddEdgeAndWeight (4, 3, 3);
  g.AddEdgeAndWeight (5, 2, 2);
  g.AddEdgeAndWeight (5, 4, 3);

  if (g.find_cycle ())
    cout << "The graph has cycle" << endl;
  else
    cout << "The graph has no cycle" << endl;

  return 0;
}

 



Related Contents to follow