This week, we're going talk about something entirely different. Instead of talking about a data structure that seems really useful for common sets of data, we're going to talk about data structure that's somewhat specialized. But it's going to have huge applications when we begin starting talking about graphs. Specifically, we're going to talk about the idea of disjoint sets. A disjoint set is going to be a series of sets which are disjoint from one another, but every single element within a set Is considered to be equivalent within that set. Let's take a look at an example to see what that means. So, here are four disjoint sets, we have one set that contains the elements two and five and nine, another set that contains the element seven, another set with the elements zero, one, four and eight and a final set with the element three and six. When we consider each of these sets, we consider every element inside of a set to be absolutely equivalent. If you're familiar with mathematics, this is something saying that these two elements are in an equivalence relationship with one another. As far as we're concerned, two, five and nine are completely indistinguishable. We can do operations on the disjoint set like the find operation. The finder four operation is going to find the set identity for the set that contains the element four. So, we can choose any single element to be the set identity or call it something completely different. Just to be really clear, I'm just going to always use the first element is my list to be the identity element for that set. So, what this means is, if we look at this set right here of two, five and nine, the identity element for this set is two, the identity element for this set here is seven, the identities element for the set zero, one, four and eight is zero, the identity element for the set three and six is three. The big idea is we need to make sure that identity element for every single set is unique, so that we can differentiate a set from one another, but we can now know that the identity of every single element in within a given set is going to be the exact same thing. So, when we find the element four, what we're going to return is, we're going to return the set identity for that element. So, here, finding four we say the set identity of that element is zero. Likewise, one operation that we need to ensure is consistent is, we need to ensure that find of four has the exact same value as find of eight. Because find of four and find of eight both need to return the same set identity because both four and eight are in the same set. In this example, we have zeros as the set identities, so both find of four and find of eight are both going to return zero, zero is equal to zero. So, we see that by choosing a set identity we can ensure when we do a find that we can find whether or not two elements are in the same set. The other operation that we're going to care about is not only do we need to find, but we may need to actually union two sets together. Once we add an element to a set, we can never separate it again. So, by unioning two sets together, what we're doing is, we're unioning the set that contains one element with the union of the set that contains another element and the end result is a larger set that contains both elements. Look at an example. Here, we're going to union the set that contains two and the set that contains seven, so the set seven contains two is going to be this top left set and the set that contains seven is going to be the top right set. When we union the set that contains two and the set that contains seven, the new set is a single set that contains all of these elements. Now, seven has a different set identity because seven is in the same set is two, five and nine, we know that the set identity for seven now must be two. Mathematically, we can talk about a set as being a collection of different sets. So, disjoint set is going to be a collection of sets where each set has a unique identity on it. As part of this set, we know that each set has a representative member and that's going to be element that uniquely identifies that set. The only operations that we're going need to program on this data structure is, we need to go ahead and make a set out of a single element, we need to find the identity of a given element set and the final thing is, we need to be able to union two sets together. We're going to dive into how we create a really incredibly efficient algorithm to solve this particular problem all of this week. So, we'll start by looking at what we can do to build the structure in the very next lecture, I'll see you there.
