Disjoint-set data structure c++ implementation
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.
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:
- find() – Determine which set an item belongs to.
- union() – Combine or merge two sets into a single set.
A simple array implementation of disjoint-data structure ( union-find algorithm)
Let 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
1 2 3 4 5 6 7 8 9 10 11 |
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]); } |
1 2 3 4 5 6 7 8 9 |
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.
disjoint set data structure c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#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; } |
Leave a Reply