Hi, everyone.
So in this video, we are going to discuss the call for the Kruskal algorithm for finding the medium
spanning tree.
So what is Google algorithm will take as input, so it will take graph as input and what is the approach
that we have discussed?
So what we need to do for each vertex, we will need to call the Miksad function that we have discussed
this many times.
We will call the Miksad function for every vertex and then what we need to do, we need to sort the
edges in increasing order of which.
Right.
We need to start and then we will pick each one by one.
And Edge should not make cycle.
So what is this function done?
So this function will written list of edges in the minimum spanning tree.
So currently in the spanning three, how many pages are there?
So obviously this set is basically empty.
We do not have any edges yet.
So we are going to read the list of ideas, but currently we don't have any idea.
So what we need to do for each edge, basically we will pick each edge and where we can see all the
edges are basically sorted in increasing order of the weights.
So we are going to pick each edge inside determiner right of the manner of bits.
So we are picking each vertex, you and vertex.
We what we need to do, we need to find out the representative element of the set.
So here we are trying to find the representative element.
So X is the representative element for Vertex you, why is the representative element for Vertex V,
if X and Y they are different, different means they belong to different said, they belong to different
connected component.
If they belong to different connected component, then this edge is safe, this X is safe, this edge
will not create cycle.
So since this edge will not cycle so we can keep these two sets.
So we need to club the cells X and Y, right.
X and Y are the representative element for their corresponding sets.
So we are calling unión function.
So we are going to keep them and what else.
So this edge will be the part of our M. spanning three.
So I will add this edge to our minimum spanning preset.
So say it was empty.
Now it will contain this edge.
And finally then we will pick each and every edge.
We will come out of this loop.
We will return misti MSD containing the set of edges.
Right.
So here I have written for clarity that we need to pick the edge only when they are in different set
so that cycle will not form so that there is no cycle.
Right.
So this is the complete code for Kruskal algorithm.
Right.
So this is it from this video.
Guys, if you have any doubt in the code, do let me know.
I will help you.
So that's all that I want to discuss in this video.
I will see you in the next one.
Thank you.