Hi, everyone.
So in this video, we are going to discuss about Prem's algorithm, Supreme's algorithm is another Iguanodon
for finding out.
Dominionist Manningtree, we have already discussed one algorithm which was kruskal to find out Dimino
spanning three Brimson liver damage and other algorithm to find out the same.
You spanning three.
So given a graph, let's see.
So this is the graph given to us and we want to find out the meaning spending.
So how primps algorithm works is we basically do three things.
For example, let me write here.
What are all the vertex we have?
So we have Vertex zero, one, two, three and four.
Right.
We have Vertex Zero.
We have Vertex one, two, three and four.
Now that think that we are to maintain our parent and build.
And also, which Naude has been visited, so let's right here visited, which all we have visited as
of now, right.
So what we do is in PIMS algorithm, we can start from any node.
So let's say this is my source note, this is my start node.
So you can pick any node as the start node or the node.
So since this is the source node, what I will do, I will assign it.
So this has a big zero and list all the nodes has it infinity.
So the word zero is picked up as the start node, the node.
So it's worth zero.
And the weight of rest of the nodes are infinity.
This is the first thing that you need to do.
Similarly, let's talk about parents.
So what is the parent of zero, Norvan, minus one?
Similarly, the parent of rest of the nodes are not determined yet.
So the parent are minus one for all of the nodes so we can initialize these values.
Similarly, I have not visited any of the node as of yet.
So my visited arrays, basically my visitor site is basically empty right now.
Let's start.
So what I will do, I will start from the source node.
I will start from this node.
And what do we need to visit each and every node who are the neighbor of the Snowden.
So we need to go to.
We need to go to every neighbor.
Every neighbor vertex.
Which is not visited yet.
Which is not visited.
Right, we need to go to every neighbor vortex, which is not visited so far, zero Jike Vortex one
has been visited or not visited that is empty and we are visiting the noticiero.
So I will put Noticiero as this note has been visited.
I am repeating myself.
I am standing at this node, so I am visiting this node.
So in the visitor, that zero node has been the vortex, zero has been visited and now I am taking its
neighbor to Vertex.
One has been visited.
Are not.
No Vertex one has not been visited.
So what I will do, I will compare this thing forward and infinity.
So four is less than infinity so I will update this to four.
So what I am taking here, I am checking this distance so I am checking the distance.
Veered between the Vortex zero and one, since the world is less than the weight of Vortex one, so
the weight of Vortex one was infinity.
So I will update infinity before I will replace infinity by a four to four vortex.
When the new world is full and with the parent, I am coming from vortex to zero.
So Vortex zero is deeper and zero has one more neighbor, which is neighbor two, vortex two.
So this is it.
And this is infinity.
So it is less than infinity.
So I will replace infinity by eight, right.
I will replace infinity by eight.
So replace infinity, replace weird by it.
And with the parent for Vortex zero I am coming from Vortex zero.
So the parent for Vortex two is vortex zero.
Simple.
Now Zero doesn't have any other neighbor.
So since zero doesn't have any other neighbor now what will do, pick the node which has the minimum
wage.
So what I need to do.
Big Naude.
Which has.
Minimum wage.
So initially, this node was having a bit of zero and list, all the nodes were having weird infinity.
That's why I paid so snoad simple.
Now I have four nodes left for two, three and four.
Let me right here, big node, which has minimum wage and is not visited yet and not visited.
So currently I have visited only one node, only one vertex for Vertex.
Still need to be visited.
So this vertex has a way to for this vertex as a weight of infinity, this infinity and this it.
So I think this is the minimum rate where it is minimum for this.
So I will visit one.
Let's visit one.
So I am visiting one.
Who all our neighbors are often right, we need to go to neighbors zero, his neighbor, but zero is
already visited, so we will not visit zero to his neighbor made to his neighbor.
So this is to this is it, too, is less than it's the place.
So for what?
Next to the new realities, too.
And this word is coming from vortex one.
One has a neighbor to this very day six, this world is infinity.
Replace infinity by six.
Who is the parent for Vertex three.
I am coming from Vertex one.
So parent is Vertex one.
One doesn't have any other neighbor.
Good.
So now again pick the node which has the minimum wage and is not visited.
So I have three nodes which are yet to be visited two, three and four.
So this has a weight of to this as a bit of sex.
This has a word of infinity.
So lets visit to write.
So big Danovitch, which has been Vertex two, has been made and it is not visited yet, so let's visit
this node.
So go to all the neighbors, go to all the neighbors of the two has a neighbor, one, but one has been
visited too, has a neighbor zero but zero is also visited to his neighbor.
Three three is not visited yet and three is less than six.
So update the with the history.
Let's update this to three.
And who is the parent of three.
Parent of three is vertex to.
Similarly, the six nine nine is less than infinity, so replace infinity by nine, so replace infinity
by nine.
And who is the parent for Vertex?
For Vertex two is the parent.
Now, two doesn't have any other neighbor, right?
So what we will do again, we will again pick the node, which has the minimum of it and is not visited.
So I have to vertex left three and four.
So these vertex has not been visited and out of them, this has less.
Wait, wait.
This has less it.
So I will pick this.
I will visit this.
So let's visit this.
So this will be zero one, two and three.
So after picking the node, what are we doing?
We are going to every neighbor.
So good to neighbor when.
But this neighbor has been visited.
Go to neighbor too.
But this neighbor has been visited.
So go to this neighbor neighborhood and check this value.
Wait, what we are doing, we are going to each and every neighbor vertex and we are checking this.
So here we do.
We have.
So this is five, five, ten, nine.
So replace nine by five, so replace nine by five.
And who is the parent sole parent updater to Vertex three three does doesn't have any other neighbor.
So good bye now pick the node which has not been visited.
So there is only one node which has not been visited yet.
So let's pick this node, let's pick this node and this will be able to answer that zero one, two,
three and four.
And now what we need to do is go to every neighbor vertex, which is not visited so far, has this neighbor.
But this has visited this vertex, his neighbor.
But this has also visited four doesn't have any other neighbor.
So we will stop.
So we will stop and how our spending tree will look like.
So this is zero.
Right.
And how do we figure out the edges?
So see, let me write the node first zero one to.
Three and four.
And let's show the value for zero, I have it zero for one, I have it for four when I have it four
four two, I have two.
For three, I have a weight of three.
ForFour, I have a very tough life and what are the connections so zero is not coming from anywhere.
One is coming from zero, so one is coming from zero for two.
I am coming from one to four to I am coming from one, four, three.
I am coming from two.
So for three I am coming from two four, four, I am coming from three to four.
I am coming from three.
So this is your minimum spanning three.
This is your spending tree and what is the total cost?
What is the total weight?
So you can add all these value zero four to three and five.
So zero plus four plus two plus three plus five.
So this is the minimum cost, right?
This is the minimum wage and this is your minimum spending.
Three.
Simple.
So that's how you can solve this problem.
That's how TPIMs algorithm works.
So can we write the algorithm?
So writing the algorithm is very simple, what we are doing here.
So we are picking every node which has the minimum wage.
So for this thing, what we can do, we can use a minimum heap.
Right.
We can use a minimum for this because each time we need to pick the node which has the minimum wage.
So it will insert all the witnesses in the heap.
And each time we will pick out the vertex, which has the minimum value, minimum wage, and then we
are going to every neighbor which is not visited.
And for every neighbor, we are checking this condition and we are updating the value of it accordingly.
Similarly, we are updating the parent.
So let let us write the code for this algorithm, which is going to be very, very simple.
So.
So this primps algorithm will take Gadhafi's input and it will also take this starting nor the source
code.
So it doesn't matter.
You can give any node as the source node.
Now, first of all, we need to initialize theories visited at your parent data and your.
So what we need to do.
For each vertex.
For each Vertex V word will be the value of parent, every parent of every node.
Minus one.
Similarly, the weights of every node is infinity.
Similarly, no one has been visited as of yet, so visited of nor will be false.
I have not listed any node, any vertex as of now, next.
But we need to do so.
We need to.
We need to change the weight value for those.
Right, so as discussed, the weight of Solis A. is going to be zero.
What else do we need to do, one more thing as discussed.
We need to insert all the vertex in the minimum rate.
So what will do?
Let me right here, so we will create create a minimum EHP.
Create a minimum heap of all Devadas.
Right, we will insert all the verdicts in the minimum so that we can get the minimum noad every time
the not having the least value of it.
So what they need to do while.
While my priority queue, let's name it, to create a minimum help, create a minimum, help you, right.
So while the queue is not empty, so while the queue is not empty.
What we do.
Pick the minimum load, so pick the minimum load, extract minimum.
All right, we will get the minimum vortex, the vortex, having the least value of it, and now we
need to visit all the neighbors.
One more thing, since we are going to visit this node.
So I need to change its value.
To visit it of you is basically true.
Now we are visiting this node, so I am setting the value visited of you to be true and go to every
neighbor, go to every neighbor, which is not visited for each neighbor.
For each neighbor, we.
Of vortex you.
What do you will do, first of all, this knowledge should not be wasted, so if the visited.
If the neighbor has not been visited.
If the neighbor has not been visited, then only I will check that condition, that if the distance
if the if the if the distance between the vertex you and V is less, then the weight, the weight of
Vertex V..
If this is the case, then you will update Vertov V to be the distance.
Between the vortex you and envy, and also you need to update the patent area.
So now the parent of V is you Vertex U.
And that's it.
So that is the complete primps and you go out to them.
I'm explaining it one more time.
Let's take one more example, let's take that example only.
Right?
So I have so I have this zero.
This was I think when this was I think to this was three and this was four.
And we have these connections.
So this was for this was it?
This was to this was six.
This was three.
This was nine.
And this was five.
Right.
So for every vertex parent is minus one.
It is Infinity Vista.
This falls.
Right.
So let me read the vortex here.
Let me read it here.
Let me read it here and let me write visited here.
And this is my priority dequeue, this is to minimum, right?
This is empty.
So initially no one is visited so empty and I initialised parent to mind this one for all world is so
vertex zero.
Vertex one.
Vertex two.
Vertex three and Vertex four.
So parent minus one.
Minus one.
Minus one and minus one.
Wait, let's talk about it.
So weird initially infinity for all of them.
So weird initially.
Infinity for all of them.
Since zero is the starting, not zero is the starting node, so it is changed to zero, so where it
is changed to zero for this Andrest, everyone has a weird infinity.
Then we are creating a minimum heap of all the witnesses, so push all the verdicts in the minimum heap
so Vertex Zero has a weight of zero.
Similarly, Vertex one has a weight of infinity vertex to infinity with vertex three infinity weight
and vertex for infinity weight.
This is your priority queue.
Then what we are doing while the priority queue is not empty, while it is containing elements, you
need to pick the minimum element each time.
So this is the minimum bid.
So I will pick this.
So remove from the priority.
You make the wisdom to be true.
So zero has been visited, right, for all the numbers.
So zero has number one and two for all the numbers.
If they are not listed, one and two are not listed, check the distance.
So distances four and four of the distances infinity.
The four is less than infinity.
Then you will update it.
So update the word for vertex one to be four because distance four is less than with infinity.
And also the parent, the parent will be updated to zero.
Right now, again, I have one more number, which is number two.
So distance eight is less than infinity distance.
It is less than infinity.
So so update the word here, update devilled here, then update the parent, which is Vertex zero.
Right.
And also you need to update here.
So for infinity now, this has been updated to four and this infinity has been changed to it.
Right now, Vertex Zero has visited all the neighbors.
So I will come out of this for loop.
I am going to come out of this for loop, and again, I will pick the minimum value from the priority.
You know, the minimum is for eight infinity infinity.
So this is minimum rate.
So remove this and visit this 081.
So you will visit this rate.
You will make the true go to all the neighbors of one.
So I will go to zero.
But zero has already been visited, so zero is visited now go to two, two is not visited.
So this distance too is less than eight distance too is less than eight.
So you will update the IT and the parent.
So you will update the will to be too and you will update the parent to be when similarly for three
distance is six less than infinity support six here but six here change parent to one.
So when I visited all the nodes I will come out of the for loop again.
We will pick the minimum, we will make the visit to be true.
Go to all the neighbors and the neighbor.
If not visited, then check the distance between them and the visit.
Every distance is less than the visit then of their parent and their child.
This algorithm will work.
So this is the code for the algorithm.
So if you have any doubt in its algorithm, you can definitely ask me in the Q&A section.
So this is it in this video.
I will see you in the next one.
Thank you.