First of all, we need to be able to check whether it joins two vertices that lie

in the same tree or in other words, that lie in the same connected component.

In this case, they lie in the same connected component, so

Kruskal's Algorithm will not edit through the set x,

because otherwise, it would produce a cycle in our set x.

Now, assume that next set that Kruskal's Algorithm tries is the following.

Again, we need to check whether the corresponding two end points lie in

the same connected component.

In this case, it is not a case.

They lie in different connected component.

So we add this edge and to this point, we should update the data structures that

we use to indicate that now we actually merge trees T1 and T2.

So what we need to check in our data structure is whether two given vertices

lie in the same set or in the same connected component, and also if they lie

in different connected components, we need to merge the corresponding two trees.

So the perfect choice for data structure for this algorithm is, of course,

the disjoint sets data structure.

Once again, to check whether two given vertices lie

in different connected components, we just check whether find of

one endpoint is equal to find of the other end point of this edge.

If they are different then they lie in different connected component.

And when adding an edge to the set X, we need to merge the corresponding two tree

and this is done by calling the method union of the corresponding two end points.

We will now illustrate this on a toy example.

This is a toy example where we have six vertices.

Let's first call them A, B, C, D, E, F, and

let's assume that we have a data structure disjoint set and

let me show the contents of this disjoint sets of this data structure.

So initially, each vertex lies in a separate set.

No we start processing edges in order of non-decreasing weight.

So the first lightest edge is AE.

We check whether A and E, at this point,

lie a different connected components.

For this way, we call find of A and find of E.

This gives us different IDs because they stay in different sets.

So we add this edge to our current solution and

we also notify our data structure that now A and

E actually lie in the same connected component.

So now it looks like this.

The next lightest edge if the edge CF.

Again we ask our data structure whether C and F belong to the same set and

each replies that they do not belong to the same set because find of C is

not equal to find of F, so it is safe to add this edge to our solution.

We also notify our data structures and C and

F now lie in the same set by calling union of C and F.

So now C and F lie in the same set.