Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph) | GeeksforGeeks

Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph) | GeeksforGeeks


Hello friends! And, welcome to GeeksforGeeks. In this tutorial we are going to cover Cycle
Detection in an Undirected graph using the Union-Find algorithm. So first we see, Disjoint-set data structure. It is basically a data structure which help
us keep track of a set of elements partitioned into a number of disjoint subsets. So if we have N elements partitioned into
subsets, it will keep track of connectivity of each element in a particular subset and
also connectivity of subsets with each other. Here you can see the three sets we have. These are disjoint set as they have no elements
in common or we can say that their intersection with each other is an empty set. So this disjoint-set supports two operations, The first is the Union() operation and, the
other one is Find() operation. So if we apply these operations on these 3
sets, the Union operation will join two subsets into a single subset. i.e Union of S1 and S2 will give us a set
containing elements of set S1 and elements of set S2. Here you can see how the two sets have merged
into one. Next we can use Find() operation to determine
which subset a particular element is in. So if we say Find(B), it will look into the
universe of sets and give us S1,similarly Find(D) will again give us S1 and Find(Z)
will give us S3. Now that we have seen how Union() and Find()
works lets see how we can use them to detect a cycle in an undirected graph. So the idea that we are going to use is that
for each unvisited edge, we make subsets using both the vertices of the edge. If both the vertices belong to the same subset
we say that we have found a cycle. Letís see, how the pseudo-code for this would
look like. Here is the code for our idea. We visit all edges one by one and for both
the vertices of the edge we use Find() operation to check which subset it belongs to. If they belong to same subset we say that
a cycle has been detected, else we do a Union() of the sets they belong
to. We’ll try using this algorithm on a sample
graph and see if it works. Here is our cyclic graph on which we will
run this algorithm. So we have these 5 nodes as shown and also
we have a parent array the entries of which are initially fix to -1. So this parent array basically help us connect
the elements that belongs to the same set, the working of this will be soon clear to
you. Initial values of -1 here means that each
element is the representative of its own set or root of its own tree. See this diagram. Here you can see how each element says that
it represents its own set, so in total we have these 5 different sets. Now recall the algorithm that we have seen
previously. We start by visiting edges. Letís begin with this edge connecting node
0 and 1. We do Find() operation on node 0 and 1. So Find(0) is 0, as 0 is representative of
its own set and Find(1) is 1 as 1 is representing its own set. Since both belong to different subsets, we
do a Union() operation and merge both the subsets. Union(0,1) would give us a set having both
{0,1}. Now here comes the use of parent array. If we make 1 as parent of 0, it can help us
track both the element of the set. So 1 is the parent of 0 and, this set is represented
by 1. We then take the next edge, letís have this
edge connecting node 0 and 2. We do Find(0) and Find(2), which comes out
to be 1 and 2 respectively. See why Find(0) is 1 is because it belongs
to a set which is represented by 1. And Find(2) is 2 because it is represented
by 2 itself. Now since they belong to different subsets,
we do a Union() operation on the two subsets. Union(1,2) will look like this. Look at the parent array, 1 is the parent
of 0, 2 is the parent of 1 and then 2 is given the task to represent this subset. Also we have 3 subsets now. One having {0,1,2} represented by 2, subset
with {3} represented by 3 and subset {4} represented by 4 itself. So again we take an edge. We choose edge connecting 1 and 3. We do Find(1) and it gives 2, and Find(3)
which gives 3. Since both belong to different subsets, we
do a union of the two sets. Union(2,3) will be like this and the merged
set would be represented by 3. Also notice the change in parent array. Now we are only left with two subsets. Next we take this edge connecting node 1 and
4. We do Find(1) and it gives 3, and Find(4)
which gives 4. Since both belongs to different subsets, we
do a union of the two sets. Union(3,4) will be like this and the merged
set would now be represented by 4. We also make 4 the parent of the node 3. Now we are only left with a single set. We now choose this last edge connecting node
3 and 4. We do Find(3) and it gives 4 , and Find(4)
which gives 4. Since both 3 and 4 belong to the same set,
we say that we have found a cycle and with this we can stop our algorithm. Here we see the implementation of what we
have discussed so far. This code on cycle-detection in undirected
graph has been taken from GeeksforGeeks. This isCycle() function takes a graph as input. It creates a parent array and also initialize
each entry to -1. Next it takes each edge one by one and then
do a Find() operation on the vertices connected by this edge. If Find() of both vertices comes out to be
same, we return 1 or true else we do Union() on both the sets to which
they belong. Here we have an implementation of Find() and
Union() operation. These are the general functions and are used
in various application of disjoint-set. So now we wrap up this tutorial. If you have any doubts or suggestions please
leave them in the comment section below. Thanks for watching!

14 thoughts to “Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph) | GeeksforGeeks”

  1. great explanation..but dude you're too slow. Please try to speak a bit faster! (otherwise, half the people will sleep while watching your videos).

  2. Since it is un-directed graph, does this algorithm work if the edge-list contains both the edges between (u, v) ?

  3. In Union function, we are already passing the sets in which the vertices of a particular edge belongs to. But in Union function, we are again calculating their parents in "xset" and "yset". I think this operation is unnecessary in Union function. Please correct me if I am wrong

  4. Sir what will happen if 3 and 4 will not contain an edge in that situation find(3)=find(4)=4 so it shows a cycle although there is no cycles

Leave a Reply

Your email address will not be published. Required fields are marked *