In this lecture we are going to begin implementing in params algorithm.
We are still in section 27 and I just went ahead and commented out all the code from.
Previous implementation of the minimum spanning tree.
That way it's just out of the way and we know that there's not going to be any conflicting code.
So to begin this implementation, we need to bring a couple of items into scope.
The first one is reverse, which I will explain when we get to there.
And the next one is going to be our B tree map and our binary heap collections.
So a lot of this should look really familiar to you because we have implemented most of this before
already.
So I'm just going to quickly go through setting it up that way.
We don't waste too much time going over it.
So we get our graph.
Now we need to add in our adding, creating our edge, and our vertex is going to again implement,
ordered and copy as well as our edge board and copy.
And here we're going to pass in our graph that we want to add the edge to.
It's going to be a mutable graph with our vertex and our edge generics.
We have vertex one, which is a Type V, our vertex two, and then we have our weight, which is our
edge.
And since this is an undirected graph, what we are going to do is go from vertex one to vertex two
and from vertex two to vertex one.
So we want to call or end cert width and we're going to have a B tree map new which calls insert, which
calls value to with weight.
And we can copy and paste this and again, reverse from vertex one to vertex two.
So our add edge function looks good now.
So now we can add in our print implementation where we're going to have our vertex implementing and
ORD and copy as well as our edge.
And we're going to pass in a graph which is going to be a reference to a graph and we need our starting
vertex
and so that we have something to compare against.
We are going to return a graph that way we have a graph to test against.
So now we're going to create a new mutable variable called MST, which is going to be a new graph and
we want to return our minimum spanning tree so we can go ahead and do that and we want to keep track
of who we have visited.
So we will say binary heap new and now we want to insert into our minimum spanning tree our starting
value and put in a new B tree map.
All right.
So now that we have inserted in our starting vertex into our minimum spanning tree, we now need to
get all of our neighbors so we can say for vertex with weight in our graph start, we want to push these
into visited and we're going to push them in and reverse order, which I will explain why in a second.
Let me.
All right.
So we push in and we need to pass this in by reference.
There we go.
So if we look at the binary heap, we say we see that it says this is going to be a max heap.
What reverse is going to allow us to do is it's going to allow us to take this max heap implementation
and turn it into a minimum heap.
And this is important because it will allow us to put all of our edges with a minimum weight first into
our minimum heap.
And if you remember from the previous lecture that that will be beneficial because we want to add all
the minimum edges into our minimum spanning tree first.
So what we can do now, and this will help tie it all together, is while we say let some and then we
need to reverse it, I'll let some weight and we'll say v, t and pre equals visited dot pop and this
is where it matters that we turned it into a minimum heap.
That way when we pop off of our minimum heap, we are getting the vertex with the edge of the minimum
weight because that's what we want to check to see if it's already in the minimum spanning tree.
So if it is, we can say we need to check if it's in the minimum spanning tree.
So if that vertex is in the minimum spanning tree, then continue.
That way we can get to the next value that we want to pop off.
That way we're continuously trying to make sure that we have the minimum edge being added into our minimum
spanning tree, because if it was not already in our minimum spanning tree, well now we're going to
add it into our minimum spanning tree by saying add in our previous, connect it to our vertex and pass
in the weight.
And once we add it in, well, now we need to get all the neighbors for that new vertex so we can say
for vertex weight in a reference to our graph and our vertex that we are now at.
If the minimum spanning tree does not contain the the key of a neighboring vortex vertex, then we want
to say visited dot push and again reverse.
That way we know that it's being added in properly of that weight, that vertex that we are our neighbor
is at and then our parent vertex and that's all we have to do.
So we are successfully looking at all the adjacent neighbors getting their minimum edges and then adding
them into the minimum spanning tree, moving to that new edge that we just added into the minimum spanning
tree, getting all of their edges and performing the same logic.
So our implementation looks pretty sound.
So we can now test this out and we will say config test, mod test.
Use super.
And now we can create our test of testing our frames algorithm.
F in test primes.
So what we need to do is create our graph.
So we will say let graph equals B tree map new.
And now we know that we need to add some edges.
So we will say add an edge to our mutable graph, start a vertex zero, go to one and our weight of
three.
So we are going to create the graph that we did in the previous lecture.
So we know we have seven edges three, four, five, six, seven.
We go from 0 to 1 with the weight of three.
We go from 0 to 2 with a weight of four.
We go from 1 to 2 with a weight of one.
To go from 1 to 4 with a weight of six.
We go from 2 to 4 with the weight of three.
We go from 2 to 3 with the weight of five, and we go from 3 to 4 with a weight of two.
So that graph is set up successfully and now we need to create an answer graph to compare our return
value to.
So we will create another new tree map.
We know we have four edges here.
We need to change the name of this.
Change the name of this graph to ants.
And we know that we go from 0 to 1.
With three, we go from 1 to 2 with a weight of one.
We go from 2 to 4
with a weight of three, and we go from 4 to 3 with the weight of two.
4 to 3 with a weight of two.
And now we need to assert equals that are prim and graph with a starting vertex of zero is equal to
our answer graph here.
And again, this graph is what we did in the previous lecture, and this was the solution we also found
in the previous lecture so we can run cargo test and we see that our test runs successfully.
So we know that our PARAMS algorithm is successfully running.
So I hope you enjoyed this lecture on primes algorithms implementation.
If you have any questions about anything that we did or on anything regarding primes algorithm or any
other minimum spanning tree that we did in this section, please feel free to ask me in the Q&A section.