1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find

the topic is disjoint sets in this video I will cover the following things first is what are disjoint sets and the operations on them then detecting a cycle see disjoint sets are useful for detecting a cycle in nondirected graph or undirected graph so we will take an example and learn how to detect a cycle in a non-directed graph then graphically how to represent these disjoint sets and how it can be represented using array and lastly the time efficient operations on disjoint sets are weighted Union and collapsing find that are based on the ranks or weights

we will see that disjoint sets are similar to sets Topic in mathematics but not exactly they are little bit change for making them useful in algorithms so the famous algorithm that uses disjoint set is cuscal algorithm which detects a cycle in a graph so let us see how these disjoint sets are different from normal sets of mathematics let us understand what are disjoint sets see here I have a nonconnected and non-directed graph there are two components it's not connected graph two components I have taken and each component I have represented it as a set set

S1 is having 1 2 3 4 these are the vertices of this component and set two is having 5 6 7 8 these are the vertices of second component so the two different components are representing two different sets and what is a disjoint here so no Vex is common here the numbers are not common here so if you take intersection of these two S1 and S2 then you will not get anything five empty set so that is disjoint disjoint set means two sets are not having having anything common then how we use them what are

the operations on them see we prefer performing only two operations that are find and Union I'll show what does it mean by these operations so first operation find I want to know Vex 5 belongs to which set it's not here yeah it's here so it belongs to set two find operation is to find out any element or a Vertex belonging to V set it's like a set membership operation also means that element is member of which set so like I want to find out seven 7even doesn't belong here okay here it belongs so it belongs

to set two then three find three find three where it is here so it is set one so that's it find operation is very simple so you have to find out in which set it belongs to so I'm showing you just mathematically later we will come to the data structure now let us look at Union operation see for showing you Union operation I'll try to connect these two with an edge I have added this Edge this Edge that is 4 to 8 so when you add an edge then what we do here is we perform

Union operation so we connected what 4A 8 we have connected Now find four four yeah it belongs to set one find eight 8 yeah here it belongs so it is in set to so find four and find 8 they belong to two different sets so perform Union S1 Union S2 so now we get a set that is 1 2 3 4 5 6 7 8 this is Union operation see in mathematics simply we perform Union on two sets but here there is a reason of Performing Union what is the reason if there is an edge

U comma V find out U it to which set it belongs and find out V to which set it belongs and if they belong to different sets then perform Union of those two sets this is the purpose of Performing union now why we are doing this let us see next I'll add one more Edge one to5 so this is 1 to5 now we don't have these sets that are union and we got a new set let us call this as set three so we have a new set those elements are gone this is the final

set now 1 comma 5 1 yes find one it's present here find five yes it is present here now both these vertices or numbers are belonging to same set and if they belong to same set means there is a cycle that's it this is the way we find out a cycle in a graph so what are the things we learn what is find operation what is Union operation and what is the purpose of Union operation then how we can know that there's a cycle in a graph if you take any Edge and both the vertices

are belonging to same set then there is a cycle in a graph so this for a very simple example I have shown you what does it mean by find and Union now we will take one example graph and we will see from the beginning how we can detect a cycle in a graph I will form all the sets right from the beginning I will add all the edges one by one let us take an example and find out how we can find a cycle how we can detect a cycle in a graph by with the

help of disjoint sets here I have taken one example graph and in this I have labeled the vertices so let us say these are some weights so just like let us find a minimum cost of spanning tree from this one otherwise you can also say that I have number them so first Edge that I'll be taking is this one then this one second one then third and fourth in this way I will include all the edges of a graph now how we can take the help of disjoint sets for finding finding a cycle let us

check see there are eight vertices I have taken a universal set with eight vertices each element you considered it as a set now let us start what we'll be doing is we will be going on taking edges including edges and forming the sets for them one by one so the first Edge is 1 comma 2 so the first Ed is 1A 2 so find one one is here and find two it is here so actually they are in Universal set so form a set for them take one and two so perform Union on one and

two so from this Universal set they are removed and they are brought into set One S one now next Edge next Edge is 3A 4 so 3A 4 three is in Universal set remove this find four this is in this Universal set remove it so form a set that is set two with three and four then third Edge 5 6 so this is 5A 6 and they belong to Universal set remove them from this there and form a set for them 5 six the next one is fourth edges 78 so take seven and 8 and

find seven it is here find eight it is here they are in Universal set form a set for them that is 7 and 8 now the next Edge after the fourth Edge this is the fifth Edge I'm going to take that is 2 comma 4 now you can see that all these vertices are removed numbers are removed they are in different sets now Now find two it's not there just forget this one find two it is here find four it is here so they are in two different sets perform Union so I will form a

new set that is set five by taking Union of these two 1 2 3 4 I have performed Union on these two sets so now you can see that Union is being performed let us go to our next Edge after 2A 4 this one 2A 4 sixth one is this one that is 2A 5 so 2 comma 5 find two so two is in this set now these are union remove them this is in set five and five is in set three perform Union of these two and form a set six so what are those

vertices 1 2 3 4 and these two 5 six see the reason of Performing Union is we are including an hedge considering an ed so this set is also gone we have a union this is also gone now we have only two sets now right now after this Edge seventh edges this one 1A 3 1 comma 3 I'll remove these sets and I'll just write two sets here find one it belongs to set six find three it belongs to same set so when they both belong to same set it means there is a cycle yes

you can see that by taking this Edge I'll be forming cycle I will highlight the edges that I have included so far see I have included these edges I have included these I have included these edges right now if I include this Edge this will form a cycle so don't include this that's how the edge which is forming a cycle don't include it we have detected one cycle let us continue after that seventh Edge the next Edge eth one is this one so eight is what six and eight 6 and 8 let us see find

six find six six belongs here find eight eight belongs to this one so they are in different sets perform union now we'll get seventh set and what is that 1 2 3 4 5 6 from this set and 7 eight from this set seven and8 from this set so these two are gone so this is also included now the last Edge remaining is n9th one 5A 7 5 comma 7 find five it is in the set find S this is also in this set both all are in same set only now as they both belong

to same set there is a cycle so this is how cuscal algorithm also uses it in the same way for finding a spanning tree like you may be knowing that in cuscal algorithm always we select a minimum cost hedge now shall we select it or not is it forming a cycle or not how we can know by checking into the sets so this was like a working of csal algorithm only now how it is done graphically and how it is represented using array that we have to see so I'll take the same graph and show

you let us quickly look at how we can show the sets graphically so I will do the same thing I have the same graph and the vertices these instead of universal set I have shown them as vertices here that is I have taken notes now will go on including the edges so the first Edge is 1A 2 if I include Edge 1A 2 you remember I was making a set as 1 2 now actually we don't need a set we are not performing mathematical operations here like intersection Union difference we are not performing that one

so what we want is just we want to dedu a cycle so we want to do it in an easy way so instead of showing it like this graphically we will take one and two basically we don't need the name of of a set we need just one representative of a set so we will make whatx one as a parent of set and two as a child if you like you can make two as a parent and one as a child also so let me show you other edges that is 3 comma 4 so if

I take 3 comma 4 and make a set 3 4 so three as a parent and four as a child of it now third set that is 5 six then set four 7A 8 I have included four edges I got four set graphically they are shown like this now let me include the next one from here you can get the clear picture Edge 2 comma 4 fifth one 2 comma 4 so where is two two is here who is the parent of two one the next is four find four four is here who is a

parent of four three so these are in two different sets so you remember we perform Union how to perform Union so we'll select one as a parent and two as a child here and it's a child is a three and four so we made the parent of one set as a child of the parent of another set so you may be asking that why didn't you select three as a parent if you want you select that one also it makes no difference it makes makes no difference whether you take three as a parent and one

you make it as a child of three it makes no difference then next one after fifth sixth one is a 2 comma 5 two is here who is the parent of this one one then five is here so they are in two different sets these are in two different sets so we'll include that five we will bring it here and six here actually these are gone I'll remove them now again one more thing here also you can ask a question why didn't you select five as a parent see here I have a strong answer that

before including this see how many nodes are there four nodes are there so weight of this set is more and this weight is less so we will make this as a parent and this as child earlier all the both the sets were having the same number of elements but now this is set 1 2 3 4 is having more number of elements 5 6 is having just two elements so this is representing this set you see 1 2 3 4 5 6 this is fifth sixth set if you remember already we have done this so

now this is gone now next is 7th one 1A 3 1 comma 3 one is the parent itself and three its parent is one so both of their parent is one only it it is one only so they belong to set one so both belong to same set so it's a cycle that's enough I'll not go further so this is how we detect whether there is a cycle or not graphically I have shown you now let us see the same thing again with the help of an array how it is done using array now I'll

show you the graphical representation as well as array representation see for representing a set we don't need the name of a set we are not performing actual Union intersection or set difference operations of mathematics we just want to perform find and Union our objective is to detect a cycle so for that for all eight vertices we will take a single array called parent and the indices are representing these eight vertices and each is having value minus one means each vertex is in its own set next to show you graphically how it looks like I have

even taken these eight notes now let us perform the same thing on this graph and see how we will represent sets in a array and also I'll show it graphically so first Edge 1A 2 1A 2 1 who is a parent of 1 minus one itself two find two go to index two and see what is there minus one so who is a parent of two itself so how much time it has taken for finding one and finding two find one it's minus one find two it's minus one so constant time so they belong to

two different sets now perform Union how we perform Union so graphically I will show I will select one as a parent and two as a child so two is a child of one so here we will write one so who is a perent of two now one and what is 1 minus one so there's a parent so if there's minus one or negative value then it's a parent now I'll do one more thing total how many nodes are there two nodes are there so instead of writing just minus one I'll write negative only so min-2

so there are two things minus shows that it's a parent and two shows that there are two nodes here that's it let us continue repeat the same thing for all of them next Ed is 3A 4 3A 4 find 3 - one itself is a parent 4 - 1 itself is a parent so for a set so who is a parent of four three and what is a three it's parent but there are two notes in this one 5A 6 third one so find five this is -1 find 6 - 1 so five here and

six here so this is five and this is min -2 now the the next Edge is this one 7 comma 8 find seven itself as a parent find 8 itself as a parent now make eight as a child of this seven or seven as a parent so this is seven and this is two till here we have finished next fifth Edge 2A 4 sorry 2A 4 find two one is a parent find four three is a parent let us do it in an array two go to two 1 go to 1 minus 2 so who

is the parent of this one one find four go to four three go to three minus 2 so who is the parent of this one three and this was one they are different parent perform Union so whom we should select as a parent one we will select it as parent so at a three I will write one then total how many nodes now four nodes so graphically three will come as a child of one and here is four that's it so that's how Union is done now let us take next one fifth now this is

sixth 2 comma 5 2 and five let us see who is a parent of two one let us look at here two it's one go to one it's Min -4 just one step we are going right it's not n time we consider it as constant time only find five five go to five minus 2 itself is a parent so for two this is a parent and for five itself is a parent now who should become the parent for both we have to perform union now unite these two so who should be comparing one or five

C what is there at one -4 what is there at five -2 whose weight is greater rank is greater weight or rank both are same only here we call it as rank also whose rank is greater one's rank is greater so let five come as a child of one so at five we write one now two more nodes are added to this so four and that minus 2 is added so it becomes sorry two more nodes are added to it that four and minus 2 it becomes six so total six nodes are here this is

how Union is performed let us go to next one after six sth 7eventh is what 7th is 1A 3 this will be interesting find one one okay here in this one itself is a parent find three three who is a parent one okay here in an array three 1 go to one minus one so the parent is same so for both one and three parent is same both our parent are same so so it means they belong to same set and it's a cycle if you include 1A 3 it will form a cycle see so

far we included these edges right we have included these edges and if we include 1 comma 3 this will form a cycle so don't include this one so that's how inclusion of any Edge will it form a cycle or not we can know it with the help of this disjoint sets I can continue you like this okay let me quickly finish the rest of them also but here 5A 6 is gone it is coming under this one now let us take next Edge 6A 8 6A 8 find six six parent is five five parent is

1 so go here in the an array let us see here also six parent is five and five's parent is one and one's parent that's one itself is the parent so one is the parent of six now what about eight find eight in this graph you can see this graphically it is seven so go to 8 and 7even go to 7 it's min-2 so this is the parent so perform Union on 1 on 7 now who is greater Min - 8 is greater this is min-2 so make this s's parent as one and add two

more nodes here and graphically show it like this 7 and 8 that's it now the last one is ninth one this is included now ninth one if I try to include five and seven find five parent is one find seven parent is one look at here five one only seven one only so for both of them parent is one so inclusion of nine will form a cycle so this is how a simple array of values are sufficient for finding whether there is a cycle or not with the help of find and Union operation that's all

with this what just one thing is remaining here see I instead of taking just minus one I was taking ranks or weight and the union was performed based on whoever weight is higher right so this is weighted union now one more term is used that is collapsing find so let me tell you one thing here see if I say find two go to two one one is negative just two steps find three go to three one at 1 minus 8 so one is a parent just two steps constant steps find four go to four go

to four it will take you to three go to three it will take you to one then here so the time is more time is more so here for some notes the time may be more you have to go along the parent and parent and parent then finally you will get the root or the main parent of a set so what we do in this situation is when we find that parent of six is five and then its parent is one so finally parent of six is one so for this we have to take multiple

steps but once we found out that the parent of six is one we don't have to keep it there only we can directly bring six under one so here also in six five is the parent five's parent is one so for six also it is one so we can directly modify this one now whenever we say find six go to index six what is find there one so at one it is negative so parent of 6 is one directly in constant time we can know parent of any element so this procedure of directly linking a

node to the direct parent of a set is called as collapsing find with collapsing find we can reduce the time for finding the same value next time first time we may be spending some extra time but next time in constant time we can get the parent now same way suppose I find 8 from 8 go to S from 7 go to one let us do it here go to 8 7 7 it's one go to one it's parent so once you know that 8 is under one so directly bring it under one so here also

we can write one so whenever you find any element you can collapse it to its direct parent so that's all how we can use array for representing this join sets and even link list can be used for doing this so for link list you can explore it I have shown about array in detail everything I have shown you when we use Link list then we have to take nodes and in the node we have to write down these index and stof index we have to keep it as a value that is the node value and

a poter to the parent poter to the next node so you can explore that by yourself that's all with a disjoint sets