In this lecture we are going to go over implementing in the minimum spanning tree algorithm.
The first thing I want you all to do is go into your cargo Tamal file and import in the disjoint sets
Dependency.
I created a new library section using cargo, new tac lib, section 27 for the section, And then inside
of that cargo file is where I have put in the disjoint sets dependencies.
So a disjoint set is a data structure that keeps track of a set of elements partitioned into a number
of disjoint subsets.
So what we're going to use this for is we're going to use union find, which comes a part of this disjoint
sets dependency.
And this union fine algorithm is going to check whether an undirected graph contains a cycle or not.
Now, if you remember from the previous lecture, that is one of the rules.
When computing a minimum spanning tree, we cannot have any cycles in our final tree.
So this is going to help us prevent having those cycles.
So now that we have disjoint sets in our cargo, Tom will file.
We can bring it into scope by saying use disjoint sets and we want to bring in union find into our scope.
So now we're going to create a couple of custom types to help us as we implement in our MST.
So we will say type node equals of type size and type weight is also going to be use size as well.
And now we're going to create a struct called Edge, where we're going to have our destination, which
is going to be our node and we're going to have our weight and that is going to be of type weight.
And now we're going to have our custom graph type, which is going to be a vector containing a vector
of type edges.
And now that we have all of our custom types set up, we can begin implementing in a function where
we can get the edges sorted by their weight.
So we can call this function edges by weight,
and we're going to pass in our graph
and we're going to return a vector that's going to contain a tuple of our node node and our weight.
And then here we will add an edge as vector
and we will say for source dest
in graph, dot itor dot enumerate.
So iterate through the entire graph and enumerate it.
And then for edge in dest, we want to push in our edges.
So edges dot push source dest.
Edge dot dest
and then edge dot.
Wait.
And then just to get rid of all these squiggly.
So it's easier to see.
We we know that we're going to return our edges here, so let's go ahead and bring those.
So since we're wanting to get our edges by weight and we now have all of our edges inside of our vector,
we can just sort them by key.
So we'll say edges sort by key.
We'll use a closure here, pass in our tuple by reference, and we don't care about the the two vertices
or our two nodes.
We only care about the weight.
So we want to sort by our weight
and that's all we have to do to sort our edges by their weight.
So you can see here is the sort by key
is an adaptive iterated merge sort inspired by Tim sort.
It is designed to be very fast in cases where the slice is nearly sorted or consist of two or more sorted
sequences.
So we can see that we're just using a iterative merge sort by using our sort by key that comes with
our vectors available methods.
So now we can create our minimum spanning tree function and we know that we need a pass in a graph.
So we're going to pass in our graph by reference and to get back our actual minimum spanning tree,
we're going to return a vector of node of two nodes and we need to put these in parentheses so that
we get our tuple back.
So we'll create our result vector that is going to be what is returned to us.
So to make sure that we don't have a bunch of red squiggles, we will go ahead and return our result
to keep everything happy.
And now we will say let mute and we will call this union find and this is going to be equal to union
find new graph dot linked.
So again, if you remember, the union fine algorithm is going to be used to check whether an undirected
graph, which is what we are going to use, contains a cycle or not.
So that is what we're doing here with Union Find.
We are checking to make sure that we are not using a graph that is going to contain a cycle so we can
say for source dest we don't care about the weight in this case and edges by weight of our graph.
So now that we have all of our edges sorted by their weight, which we are getting by calling this,
we can say if not union find dot equiv.
So determines whether two elements are in the same set.
So we're going to see if source and dest are in the same set.
And if they're not, then we want to union find union and that is going to join the sets of the two
given elements.
So and then it's going to return whether anything changed.
So if the sets were different, we return true.
Otherwise return false.
So we will unionize the two sets from source and dest, and then we will push this result onto our vector.
So we will say source and dest
and it looks like it's We need to make it mutable.
There we go.
All right, so that's all we have to do, because our union fine algorithm that we brought in is doing
a big chunk of the workforce by just making sure that we don't have that that cycle in our graph.
And then we're getting all the edges by their weight here.
So now we're able to check to see if that's the set that we're trying to unionize is already in our
tree.
And if it is, then that would mean that we have a cycle.
So we don't want to do that.
So now we can test this out by saying config
test mod test use super
in test F in test minimum spanning tree.
And so what I want to do is use the graph from our previous lecture.
So just so that we have a refresher on it, this is the graph that we're going to use right here.
So we're going to create that for our test case.
So we will say let graph is equal to VEC.
This is going to be that graph zero node zero.
So we have vec
edge dest one, weight three.
Edge
dest three weight six.
And lastly, for Node zero, we have Edge desk five, weight two.
All right, now we have our next VC.
So our next node that we're entering and this is Node one.
And then just for the sake of time, I already typed this out.
I just wanted you to kind of see how it's working.
So I will just go ahead and paste in the rest.
That way.
You're not getting bored watching me type all this in.
And let's see who is not happy here.
Closing delimiter.
Let me just copy the entire.
There you go.
That should be happier.
Now, what did I.
Not close?
Let's see what we got.
Singh structured fields.
DST.
There we go.
It looks like we have one more.
Get rid of that guy.
All right, so now we're good.
We have our graph set up.
So again, what we have is our graph that we created here in the previous lecture, and we hooked it
up right here.
So if we see node node zero, we go from zero to destination one.
So node one with the weight of three, node 0 to 3 with a weight of six and node 0 to 5 with a weight
of OOP.
I need to fix that.
That is a weight of one.
Let's bring it back up.
All right.
Now we have Node one going from 1 to 3 with the weight of five, node 1 to 5 with a weight of four and
1 to 2 with a weight of one.
That is correct.
Node three or excuse me, No.
2 to 3 with a weight of two and 2 to 4 with the weight of three.
Node three goes to four with the weight of seven and Node four.
Goes to five with the weight of two.
So you can see that we have one, two, three, four, five, six, seven, eight, nine, ten edges.
And we have one, two, three, four, five, six, seven, eight, nine, ten edges here as well.
So our graph looks like it is properly set up.
And so now we can test this out.
We can say assert equals.
And what we want to pass in here is.
Our vic that we want to compare it to.
So we will have in here 1 to 2.
0 to 5.
2 to 3.
4 to 5.
And 0 to 1.
And we want to compare this to MST and graph.
So now if we run cargo test, we see that we have a failed here and we said that we were going 1 to
2 0 to 5.
So I have these two backwards.
And if we look at our graph here.
0 to 5?
That is correct.
1 to 2?
That is correct.
2 to 3?
That is correct.
4 to 5.
That is correct.
And 0 to 1.
So I just had these two in reversed order.
So let me fix that real quick and then we will do this by hand just to verify that this is correct.
Clear cargo test.
So now our test is pass.
So if we look at.
Our output of.
And we will draw this very slowly so that we can see everything.
So we have zero one, two, three, four and five.
We're going from 0 to 5 one 1 to 2.
That is one, 2 to 3 two.
4 to 5.
That is also two and 0 to 1, and that is three.
So as you can tell what we have here and our vector, it is returning our values with the least amount
of weighted edges first.
So that's why we went 0 to 1 or 0 to 5, 1 to 2, because these have edges of weight, one, 2 to 3,
4 to 5.
And then lastly, 0 to 1 is weight three.
So we have a one, two, three, four, five, six, seven, eight, nine weights.
Well, we see that we have a slightly different output than what we did in the previous lecture where
we went from 2 to 4 instead of 0 to 1.
But if you look, the output is the same.
So we had two minimum spanning trees that we could have used from here, and our union fine algorithm
just went with 0 to 1 because it appears that these nodes came first in the tree, meaning that the
nodes values were compared.
So we have 0 to 1 and those were less than 2 to 4.
So it just arbitrarily picked 0 to 1.
But what we're able to see is that our minimum spanning tree did in fact work and we were successfully
able to create a minimum spanning tree with a weight of nine, which is what we concluded our minimum
spanning tree should have in the previous lecture.
So if you have any questions about this lecture, please feel free to ask me in the Q&A section and
I will see you in the next lecture when we start talking about primes algorithm.