In this lecture, we are going to begin discussing primes algorithm.
And the last lecture we went over an implementation for crew schools algorithm for a minimum spanning
tree and primes is very similar to CRU schools.
It's going to help us find a minimum spanning tree and Primes is going to start at a single node and
then it's going to move through the several several adjacent nodes in order to explore all of the connected
edges along the way.
And that's the general premise to how primes works.
So what we can do is we can create ourself a little graph and we'll say we have Node zero, node one,
two, three and four, and now we can draw all of our edges.
It was provide them weights.
So we have three, four, one six, three, five and two.
So what we can do is we can say our minimum spanning tree visited or vertex excuse me, parent node
and then the weight.
So we know that we're starting out at well, we're going to start out at vertex zero.
So this will be our start.
We don't have a parent and there's no weight given that this is our starting vertex.
So from vertex zero, we will look at all of the neighbors, vertex zero, and we see that we have one
and two.
Two has a weight of four and one has a weight of three.
So for vertex one, we will say the parent is zero and the weight is three.
So we can have our visited section over here and we've currently visited zero and one from one.
Our neighbors are four and two and we see that two has a weight of one.
So for vertex two we say the parent is one and the weight is one.
And then we have vertex three and four.
So from vertex two and let's add it in here for vertex two, we can get to zero one, four and three.
Well, we already know that we have visited one and zero, so we don't have to worry about those.
So all we have to worry about now is two or four and three and we see three has a weight of five, and
four has a weight of three.
So the parent to vertex four will be two and the weight will be three.
And now at four we see that we can get to one, two and three, but we have already visited one and
two.
So the last vertex for us to go to is three.
So we can just go ahead and assume our parent is four and our weight is two.
And now we have a minimum spanning tree that looks something like this.
So we go from 0 to 1 down to 2 to 4 and down to three.
And this is what our minimum spanning tree looks like in the solution.
So now in the next lecture we will begin implementing in premise algorithm, and then we will use this
graph as our test case to ensure that this is the output that we are able to deduce during our test.
So I'll see you in the next lecture when we begin implementing in premise algorithm.