Hi, everyone, welcome to this new video.
So in this video, we are going to discuss the algorithm for Kruskal.
So this is basically for finding out the minimum spending rate.
The algorithm is basically greedy algorithm.
So algorithm basically involved just two step.
So first step algorithm is basically what you will do.
You will start the edges.
We will sort the edges in increasing order of rates, so, for example, here are rates nine, then
five, then 10.
So we are going to sort the edges on basis of which second is basically what they will do.
You will pick the edge.
You will pick these sorted edges one by one.
So we are going to pick these sorted edges one by one, and we will add them in the minimum spending
three.
But the condition is edge should not make a single big.
These is only if it is safe.
So what do I mean by a safe safe means cycle should not be there.
Pecl not pleasant by picking the edge.
They should not be cycle in the spending tree.
Right.
Let me write it clearly.
These are teenagers.
And.
Edge should not make cycling.
This is better and should not make a second.
So these two other steps of critical algorithm, very, very simple algorithm.
So let me run these steps on this example.
So this is a graph, right?
This is a graph given to us.
We need to find out the minimum spending tree and let's use algorithm.
So what this is, it is sort of the edges.
OK, so let's say I have sorted edges.
I have sorted all the edges based on their weight.
Now, what we need to do, we need to pick these sorted edges one by one.
So what is the minimum wage here?
So this is 11, five, 10 minimum wage.
Is this one right?
This is the minimum wage.
This is the minimum wage, so I will pick this age, let's pick this age.
So I am picking this edge in our spending tree, so this is my minimum spending tree, so in my spending
tree I have decided that there will be an edge.
I have selected for stage, for entry and the way this tree.
Right.
So we have the edge.
And currently there is no cycle, right.
There is no cycle.
This is about amnesty for entry.
No cycle is there.
Or what can I do.
For better understanding, let me write for entry here four and three, so I have picked this edge.
Now let's pick the second.
You can see this is not making any second, right.
There is no cycling domestic.
Now, let's pick the second minimum wage.
So after three, this is six, seven, ten.
I think five rate five is the minimum wage right now.
So let's pick this age.
Let's pick this age, which is zero and two, so I am picking the age zero.
To to hear the story and hear the it is five.
OK, so currently this is our amnesty and amnesty.
There is no cycle right now.
Let's pick the third age.
We are picking the age in this hour, 30 minutes or the third age after three and five.
I think it is six, right?
It is six years.
So let's pick this age.
Let's pick this age, so if I pick the edge, if I pick this age the way it is six and there is no cycle,
so currently there is no cycle present in our midst.
So I can pick this age now let's pick the next age.
So after six, I think seven.
So let's try to pick this age.
So if you will pick this age right, if you will pick this age, then there will be a cycle.
A cycle will be formed.
If you pick this age seven, that means you cannot pick this age.
Right.
What is the condition after picking the age check whether there is a cycle or not.
If you will pick this age seven, then a cycle will be formed in the middle of spanning spending.
Three and we do not want cycle spanning three are basically acyclic.
So we cannot pick this age.
I cannot pick this age.
So let's move on to the next edge that I can pick.
So after seven I can pick ten made.
Ten is minimum so I can pick ten.
So after picking ten, yes I can pick ten because they will be no cycle.
So I can pick ten because there is no cycle introduced because of picking this age right now after ten
which edge I can pick so.
Sorry, sorry, sorry.
This is, this was nine.
Please forgive me.
Actually this was nine so we need to pick nine first.
We will not, we will not pick this will first pick nine.
After seven after seven we will pick nine.
Nine is minimum.
So let's pick nine.
So after picking nine there is no second introduced so we can pick nine.
Nine is safe.
Twelve.
This is nine now after nine, which is gigantic, so this is 10, 11 and 12, so three are remaining.
If I pick this age 10, if I pick this age 10, then what will happen?
They will be cycle introduced in your spending.
Three, and we do not want a cycle.
That means I cannot pick 10.
So after 10, let's talk about 11.
So if I pick this age, then there will be a cycle introduced so I cannot pick 11.
So let's move on to 12.
So if I pick this age 12, if I pick this age 12, then what will happen today will be the cycle introduced
zero to one one, two, three, three to four, four, two, two and two to zero.
Right.
So in this way, zero two one one, two, three three to four four two two and two two zero.
So they will be a cycle introduced.
So I cannot pick one.
And that's all we have picked all the ages.
And this is our minimum spending tree.
This is our minimum spending spree.
And in this spending spree, so there are how many roads present?
One, two, three, four, five, five nodes at present.
So how many items should be there and spending three, four edges should be there in spending three.
And we can see there are four Reges rate.
So this is your minimum spending three.
Right.
So I have highlighted here also we have picked this age, we have picked this age, we have picked this
age and we have picked this age.
So this is our medium spanning three.
Right.
So that's how Kruskal algorithm works.
What is the total cost?
This is nine plus nine plus five plus six plus three.
Nine plus five plus six plus three.
That is 23.
So 23 is the minimum cost.
Right now, let's take one more example.
Let's talk about this example.
So what do we need to pick the ideas in SA today?
So what is the minimum age?
So I think this is the minimum age.
Is this one one?
This is the minimum wage.
So let's pick this age.
So after picking this age, there is no cycle so we can pick this age now after one, which is just
the minimum.
So I think we have to here and we have to here also so we can pick any one of them.
I can pick this or I can pick this rate.
They both are equal.
So you can pick any of them.
Let's say I am picking this one.
Since they both are equal, so you can pick any one of them, so if I am picking this.
So after picking this age, there is no cycle introduced in the graph, there is no cycle in reducing
the tree.
So you can pick this age now after two.
I need to pick this.
So if I pick this, can I pick this?
Yes.
There is no single introduced.
So you can pick this age now after two, which is the minimum age.
So food and we have food here also.
So again, you can pick any one of them in any order.
So if I pick this age so after picking this age, is there any cycle.
So can I pick this age?
Yes, I can pick this age.
There is no cycle introduced.
So this is yes.
There is no cycle introduced.
So I can pick this age four.
So after picking food, this is the next smallest rate.
So let's pick this age.
So after picking this age again, there is no cycle introduced so you can pick this age.
So after four which edge I can pick to eight 11 seven.
What is the minimum after four.
I think it is seven seven.
Yes.
So I have seven here and sorry we have six right after four we need to pick six.
So if I pick this age, if I pick this age, then what will happen.
There will be cycle introduced.
There will be a cycle introduced in the spending tree, so I cannot pick this age, so I cannot pick
this age between eight and six with the weight six.
So after six, what is the next smallest rate?
It is seven and seven is present here as well as seven is present here.
So can I pick this age?
Yes, I think I can pick this age because there will be no cycle introduced.
No, no, no, no.
They will be cycle introduced because it will pick this age.
Then they will cycle like this from here, then this, then this, then this and then basically this.
So you cannot pick this age, right.
You cannot pick this age because this will introduce cycle in your spending tree.
So you cannot pick this age.
Now let's talk about this age, the seven.
So can I pick this age?
Yes, I can pick this age.
There will be no cycle introduced.
So I can pick this age.
Find.
OK, so after 7:00, the next is basically eight, so it is present here as well as here.
So let's first talk about this.
So can I pick this edge?
So if I pick this, will there be any cycle?
Oh, no, I don't think there will be any cycle.
So I can pick this.
There is no second introduced, so I can pick this age.
OK, after it, I have this it so if I pick this age, will there be a cycle?
So let's see whether there will be a cycle or not.
Yes.
If you will pick this age, they will be a cycle introduced.
How?
Because you can see 021 then this.
Then basically this one.
Then this one.
And then this one.
So if you will pick this age, they will be introduced.
So you cannot pick this age.
We cannot pick the edge it.
Now, let's move on to the next one.
So after eight, I think I have nine.
Right.
We have nine here.
So can I pick this age?
Yes, I think I can pick this age.
There will be no cycle introduced.
So let's pick this age.
So after nine, the minimum is, I think, 10.
So can I pick 10?
So if you will pick this age, they will be introduced.
How you can see this, then this, then this and then this.
So you cannot pick 10.
We cannot pick this edge this week.
Then after 10, I think the minimum is 11.
So we.
Can you pick this age?
No, they will be cycle introduced like this.
So you cannot pick 11.
So after 11, the last remaining Verity's 14.
Can you pick 14?
No, you cannot pick 14 because in that case you will have a cycle like this.
And we are done and we are done.
So how our minimum spending will look like.
So this is zero after zero.
I have one here, I have seven here for seven.
I have six here.
Then I have five here.
So here I have two, then I have three, then I have four and then I have eight.
So this is our minimum spanning three and these are weights four eight one two four, seven, nine and
two.
So this is our minimum spending three and these are all node's.
For finding out the cost, for finding out the minimum cost of what you will do, you will add all the
values, you will add four eight one two four, seven, nine and two, and that will be your minimum
cost.
So this is a spending tree.
How many nodes are present?
So one, two, three, four, five, six, seven, eight, nine, nine nodes out there.
So how many ideas should be there?
Eight edges should be there.
So let's count whether it is at present or not.
So one, two, three, four, five, six, seven and eight.
So eight edges are there, nine nodes out there.
And the three is basically connected.
You can see this is connected and there is no cycle.
Right.
So that's how you can use an algorithm.
So you can see the algorithm is very, very simple to do.
You need to sort the edges and you need to pick the edges in sort that way.
And after picking the edge, check whether there is a cycle or not.
If there is a cycle, do not pick.
If no cycle, then pick.
Right.
Now, let's talk about the third example.
So now let's apply them on this example, on this graph.
So, again, very simple.
Pick the minimum wage.
This is the minimum wage and this is safe.
Say there is no cycle introduced after picking this age.
So let's pick this age.
Now, after one month is the minimum wage, so I have to here, I have to here so you can pick in any
order.
Let's see if I pick this so I can pick this.
There will be no cycle.
So let's pick this now after two, the first two.
So let's pick this because there is no cycle after taking after picking this age.
So after two days, the minimum wage to is the minimum wage.
So we can pick this because there is no cycle introduced after picking this age to decide just save.
So after three, I have five.
So can I pick five?
Yes, I can pick five because there is there will be no cycle introduced.
So let's pick five.
After five, the minimum is seven, can I pick seven, you cannot pick seven because in that case they
will recycle introduced so you cannot pick seven now after seven.
I have it here and I have it here so you can pick in any order.
So let's see if I pick this edge.
So if I pick this age, they will be cycler, not.
There will be no cycle, so you can pick this one.
There will be no second, so you can pick this eight.
Now I've done it, this is it.
So can I pick this?
No, you cannot pick this way because in that case, there will be a cycle introduced.
So you cannot pick it here.
Now, hear, what we have seen is if you would have if you take it first, then you cannot pick this
age.
OK, so what is happening here?
I took this age then I'm not able to pick this age.
Right, because they will be introduced.
No, if I did the opposite.
If I pick this age first and this age later, then I cannot pick this age, because in that case also
they will be a cycle formed.
So here they are.
Possibility that to a and be there.
So in that case to a mouse, they will be there.
So first, let us finish this problem, then I will discuss this, that there are two and possible in
this case.
So after the minimum value is ten, so can I pick ten?
So if you will pick ten, what will happen?
If you will pick this edge?
If you will pick this age, then they will be introduced.
How this, then this, then this, then this and then this.
So you cannot pick 10.
So your MSA will look like this zero.
Then when?
Then three.
Thenceforward.
Then to.
Then six.
And then five, so this is you're one of the minimum spending, three, you are other minimum spending
can be zero.
When?
Three.
For.
To.
Six, five.
So what do you do, you will pick this.
See, I told you, these are the same, so if you will pick this, you are not able to pick this.
If you pick this first, then you are not able to pick this.
So there are two many spanning, three possible.
Right.
So here I have it.
And here also I have it addressed.
All the values that same as all the values are saying this is five.
This is three.
This is seven.
So he decides to listen to the as to the cease fire.
If this is three, this is one.
This is one.
This is two and this is two.
So there are two more possible.
And both have the same cost.
Both have the same cost, because the only thing that is changing is basically this edge.
So this is it.
And this edge also has a weight of it.
So there are two made possible in this example.
Right.
So again, you can see how many nodes out there.
One, two, three, four, five, six, seven, seven nodes are there.
So how many Edgett should be put into them in spending?
Three.
Six edges should be there.
You can count one, two, three, four, five and six.
So that is you spending three to minimize spending are possible in this case.
Right.
So I hope you have understood what this critical algorithm, how Kruskal algorithm works.
So algorithm, what is the difficult step to implement?
I think this step is pretty much simple, right?
This step is very simple, sort of the edges on both sides of it.
So this is very, very simple.
The difficult task in Kruskal algorithm is basically this.
You are picking the edge and then you need to check whether after picking the edge, there is cycle
or not.
So basically the problem here is we should have an algorithm for cycle detection.
Right, we must have one algorithm for cycle detection.
Again, I'm repeating myself in there are two parts, first, you need to sort the edges, then what
to do, you will pick edge, you will pick this that you will pick the sorted edges one by one, and
then you will check whether there is a cycle present or not.
So we need this algorithm.
If we have this algorithm cycle detection, then we can implement algorithm.
Do you agree or not?
Yes, you should agree.
Right.
So the problem is we should have an algorithm for cycle detection and graph.
Right.
So in next video, we will discuss how we can use how we can have an algorithm for cycle detection and
the name of the algorithm is basically disjointed.
We can use this joint set for cycle detection, so in next video, we will be discussing Disjoined said,
right.
So this is it from this video, guys.
I will see you in the next one.
Thank you.