1
00:00:06,320 --> 00:00:12,320
In this lecture we are going to go over implementing in the minimum spanning tree algorithm.

2
00:00:12,770 --> 00:00:19,970
The first thing I want you all to do is go into your cargo Tamal file and import in the disjoint sets

3
00:00:19,970 --> 00:00:20,960
Dependency.

4
00:00:22,310 --> 00:00:31,520
I created a new library section using cargo, new tac lib, section 27 for the section, And then inside

5
00:00:31,520 --> 00:00:38,300
of that cargo file is where I have put in the disjoint sets dependencies.

6
00:00:39,020 --> 00:00:47,750
So a disjoint set is a data structure that keeps track of a set of elements partitioned into a number

7
00:00:47,750 --> 00:00:50,300
of disjoint subsets.

8
00:00:50,480 --> 00:00:58,670
So what we're going to use this for is we're going to use union find, which comes a part of this disjoint

9
00:00:58,670 --> 00:01:00,020
sets dependency.

10
00:01:00,950 --> 00:01:08,900
And this union fine algorithm is going to check whether an undirected graph contains a cycle or not.

11
00:01:09,110 --> 00:01:12,320
Now, if you remember from the previous lecture, that is one of the rules.

12
00:01:12,320 --> 00:01:21,230
When computing a minimum spanning tree, we cannot have any cycles in our final tree.

13
00:01:21,230 --> 00:01:25,400
So this is going to help us prevent having those cycles.

14
00:01:26,840 --> 00:01:31,940
So now that we have disjoint sets in our cargo, Tom will file.

15
00:01:31,970 --> 00:01:40,880
We can bring it into scope by saying use disjoint sets and we want to bring in union find into our scope.

16
00:01:42,020 --> 00:01:48,950
So now we're going to create a couple of custom types to help us as we implement in our MST.

17
00:01:49,250 --> 00:01:58,460
So we will say type node equals of type size and type weight is also going to be use size as well.

18
00:01:59,060 --> 00:02:05,000
And now we're going to create a struct called Edge, where we're going to have our destination, which

19
00:02:05,000 --> 00:02:11,510
is going to be our node and we're going to have our weight and that is going to be of type weight.

20
00:02:14,930 --> 00:02:21,440
And now we're going to have our custom graph type, which is going to be a vector containing a vector

21
00:02:21,440 --> 00:02:22,790
of type edges.

22
00:02:24,590 --> 00:02:30,560
And now that we have all of our custom types set up, we can begin implementing in a function where

23
00:02:30,560 --> 00:02:35,220
we can get the edges sorted by their weight.

24
00:02:35,240 --> 00:02:42,350
So we can call this function edges by weight,

25
00:02:45,950 --> 00:02:47,780
and we're going to pass in our graph

26
00:02:51,170 --> 00:02:57,710
and we're going to return a vector that's going to contain a tuple of our node node and our weight.

27
00:03:03,350 --> 00:03:06,890
And then here we will add an edge as vector

28
00:03:10,280 --> 00:03:12,980
and we will say for source dest

29
00:03:16,280 --> 00:03:21,050
in graph, dot itor dot enumerate.

30
00:03:21,050 --> 00:03:25,460
So iterate through the entire graph and enumerate it.

31
00:03:25,970 --> 00:03:33,380
And then for edge in dest, we want to push in our edges.

32
00:03:33,380 --> 00:03:40,490
So edges dot push source dest.

33
00:03:43,050 --> 00:03:46,650
Edge dot dest

34
00:03:49,230 --> 00:03:50,550
and then edge dot.

35
00:03:50,550 --> 00:03:51,180
Wait.

36
00:03:56,340 --> 00:03:57,990
And then just to get rid of all these squiggly.

37
00:03:57,990 --> 00:03:59,010
So it's easier to see.

38
00:03:59,010 --> 00:04:03,300
We we know that we're going to return our edges here, so let's go ahead and bring those.

39
00:04:03,720 --> 00:04:11,010
So since we're wanting to get our edges by weight and we now have all of our edges inside of our vector,

40
00:04:11,010 --> 00:04:12,600
we can just sort them by key.

41
00:04:12,600 --> 00:04:16,410
So we'll say edges sort by key.

42
00:04:19,140 --> 00:04:26,370
We'll use a closure here, pass in our tuple by reference, and we don't care about the the two vertices

43
00:04:26,370 --> 00:04:27,660
or our two nodes.

44
00:04:27,660 --> 00:04:28,860
We only care about the weight.

45
00:04:28,860 --> 00:04:31,110
So we want to sort by our weight

46
00:04:34,950 --> 00:04:39,330
and that's all we have to do to sort our edges by their weight.

47
00:04:40,560 --> 00:04:44,370
So you can see here is the sort by key

48
00:04:47,490 --> 00:04:51,750
is an adaptive iterated merge sort inspired by Tim sort.

49
00:04:52,260 --> 00:04:57,630
It is designed to be very fast in cases where the slice is nearly sorted or consist of two or more sorted

50
00:04:57,630 --> 00:04:58,680
sequences.

51
00:04:59,910 --> 00:05:08,460
So we can see that we're just using a iterative merge sort by using our sort by key that comes with

52
00:05:08,460 --> 00:05:12,060
our vectors available methods.

53
00:05:13,620 --> 00:05:19,140
So now we can create our minimum spanning tree function and we know that we need a pass in a graph.

54
00:05:19,140 --> 00:05:25,560
So we're going to pass in our graph by reference and to get back our actual minimum spanning tree,

55
00:05:25,560 --> 00:05:33,630
we're going to return a vector of node of two nodes and we need to put these in parentheses so that

56
00:05:33,630 --> 00:05:35,370
we get our tuple back.

57
00:05:39,240 --> 00:05:44,490
So we'll create our result vector that is going to be what is returned to us.

58
00:05:44,730 --> 00:05:51,270
So to make sure that we don't have a bunch of red squiggles, we will go ahead and return our result

59
00:05:51,900 --> 00:05:53,490
to keep everything happy.

60
00:05:53,820 --> 00:06:03,150
And now we will say let mute and we will call this union find and this is going to be equal to union

61
00:06:03,150 --> 00:06:07,660
find new graph dot linked.

62
00:06:09,120 --> 00:06:16,560
So again, if you remember, the union fine algorithm is going to be used to check whether an undirected

63
00:06:16,560 --> 00:06:21,660
graph, which is what we are going to use, contains a cycle or not.

64
00:06:22,620 --> 00:06:24,960
So that is what we're doing here with Union Find.

65
00:06:24,960 --> 00:06:34,680
We are checking to make sure that we are not using a graph that is going to contain a cycle so we can

66
00:06:34,680 --> 00:06:43,440
say for source dest we don't care about the weight in this case and edges by weight of our graph.

67
00:06:43,440 --> 00:06:52,320
So now that we have all of our edges sorted by their weight, which we are getting by calling this,

68
00:06:52,650 --> 00:06:58,110
we can say if not union find dot equiv.

69
00:06:58,200 --> 00:07:01,400
So determines whether two elements are in the same set.

70
00:07:01,410 --> 00:07:06,600
So we're going to see if source and dest are in the same set.

71
00:07:08,700 --> 00:07:17,430
And if they're not, then we want to union find union and that is going to join the sets of the two

72
00:07:17,430 --> 00:07:18,150
given elements.

73
00:07:18,150 --> 00:07:21,000
So and then it's going to return whether anything changed.

74
00:07:21,000 --> 00:07:24,300
So if the sets were different, we return true.

75
00:07:24,330 --> 00:07:26,160
Otherwise return false.

76
00:07:26,160 --> 00:07:37,410
So we will unionize the two sets from source and dest, and then we will push this result onto our vector.

77
00:07:37,620 --> 00:07:40,260
So we will say source and dest

78
00:07:44,220 --> 00:07:46,660
and it looks like it's We need to make it mutable.

79
00:07:46,680 --> 00:07:47,550
There we go.

80
00:07:49,350 --> 00:07:56,220
All right, so that's all we have to do, because our union fine algorithm that we brought in is doing

81
00:07:56,220 --> 00:08:04,230
a big chunk of the workforce by just making sure that we don't have that that cycle in our graph.

82
00:08:04,230 --> 00:08:07,860
And then we're getting all the edges by their weight here.

83
00:08:07,860 --> 00:08:17,790
So now we're able to check to see if that's the set that we're trying to unionize is already in our

84
00:08:17,790 --> 00:08:18,390
tree.

85
00:08:18,390 --> 00:08:21,720
And if it is, then that would mean that we have a cycle.

86
00:08:21,720 --> 00:08:22,860
So we don't want to do that.

87
00:08:23,430 --> 00:08:28,950
So now we can test this out by saying config

88
00:08:31,470 --> 00:08:37,050
test mod test use super

89
00:08:40,110 --> 00:08:45,540
in test F in test minimum spanning tree.

90
00:08:46,230 --> 00:08:51,480
And so what I want to do is use the graph from our previous lecture.

91
00:08:51,810 --> 00:08:57,630
So just so that we have a refresher on it, this is the graph that we're going to use right here.

92
00:08:57,630 --> 00:09:02,520
So we're going to create that for our test case.

93
00:09:02,520 --> 00:09:06,660
So we will say let graph is equal to VEC.

94
00:09:09,720 --> 00:09:14,070
This is going to be that graph zero node zero.

95
00:09:14,070 --> 00:09:15,330
So we have vec

96
00:09:17,640 --> 00:09:24,960
edge dest one, weight three.

97
00:09:31,670 --> 00:09:32,540
Edge

98
00:09:34,580 --> 00:09:39,860
dest three weight six.

99
00:09:42,400 --> 00:09:48,970
And lastly, for Node zero, we have Edge desk five, weight two.

100
00:09:53,740 --> 00:09:58,000
All right, now we have our next VC.

101
00:09:58,750 --> 00:10:03,550
So our next node that we're entering and this is Node one.

102
00:10:04,060 --> 00:10:08,270
And then just for the sake of time, I already typed this out.

103
00:10:08,290 --> 00:10:11,200
I just wanted you to kind of see how it's working.

104
00:10:11,200 --> 00:10:13,900
So I will just go ahead and paste in the rest.

105
00:10:13,900 --> 00:10:14,590
That way.

106
00:10:14,590 --> 00:10:18,100
You're not getting bored watching me type all this in.

107
00:10:18,220 --> 00:10:22,030
And let's see who is not happy here.

108
00:10:24,390 --> 00:10:26,460
Closing delimiter.

109
00:10:27,060 --> 00:10:29,670
Let me just copy the entire.

110
00:10:33,780 --> 00:10:34,530
There you go.

111
00:10:35,490 --> 00:10:38,070
That should be happier.

112
00:10:38,100 --> 00:10:39,330
Now, what did I.

113
00:10:39,360 --> 00:10:40,350
Not close?

114
00:10:41,640 --> 00:10:42,960
Let's see what we got.

115
00:10:43,940 --> 00:10:46,070
Singh structured fields.

116
00:10:51,800 --> 00:10:52,760
DST.

117
00:10:52,790 --> 00:10:53,510
There we go.

118
00:10:55,130 --> 00:10:57,780
It looks like we have one more.

119
00:10:57,800 --> 00:10:59,150
Get rid of that guy.

120
00:11:00,440 --> 00:11:01,630
All right, so now we're good.

121
00:11:01,640 --> 00:11:03,140
We have our graph set up.

122
00:11:03,140 --> 00:11:12,860
So again, what we have is our graph that we created here in the previous lecture, and we hooked it

123
00:11:12,860 --> 00:11:16,310
up right here.

124
00:11:16,310 --> 00:11:21,740
So if we see node node zero, we go from zero to destination one.

125
00:11:21,740 --> 00:11:31,640
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

126
00:11:31,640 --> 00:11:32,800
of OOP.

127
00:11:32,810 --> 00:11:34,130
I need to fix that.

128
00:11:34,130 --> 00:11:37,250
That is a weight of one.

129
00:11:41,150 --> 00:11:42,290
Let's bring it back up.

130
00:11:43,600 --> 00:11:44,230
All right.

131
00:11:44,710 --> 00:11:56,830
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

132
00:11:56,830 --> 00:12:00,250
1 to 2 with a weight of one.

133
00:12:00,580 --> 00:12:01,430
That is correct.

134
00:12:01,450 --> 00:12:03,640
Node three or excuse me, No.

135
00:12:03,640 --> 00:12:09,220
2 to 3 with a weight of two and 2 to 4 with the weight of three.

136
00:12:10,210 --> 00:12:16,510
Node three goes to four with the weight of seven and Node four.

137
00:12:17,410 --> 00:12:19,390
Goes to five with the weight of two.

138
00:12:19,570 --> 00:12:26,980
So you can see that we have one, two, three, four, five, six, seven, eight, nine, ten edges.

139
00:12:26,980 --> 00:12:34,570
And we have one, two, three, four, five, six, seven, eight, nine, ten edges here as well.

140
00:12:34,660 --> 00:12:38,050
So our graph looks like it is properly set up.

141
00:12:39,100 --> 00:12:41,760
And so now we can test this out.

142
00:12:41,770 --> 00:12:44,020
We can say assert equals.

143
00:12:45,010 --> 00:12:49,360
And what we want to pass in here is.

144
00:12:50,660 --> 00:12:54,260
Our vic that we want to compare it to.

145
00:12:54,260 --> 00:13:01,340
So we will have in here 1 to 2.

146
00:13:04,370 --> 00:13:06,290
0 to 5.

147
00:13:09,470 --> 00:13:10,550
2 to 3.

148
00:13:12,680 --> 00:13:14,030
4 to 5.

149
00:13:16,580 --> 00:13:17,810
And 0 to 1.

150
00:13:23,610 --> 00:13:28,740
And we want to compare this to MST and graph.

151
00:13:30,030 --> 00:13:41,180
So now if we run cargo test, we see that we have a failed here and we said that we were going 1 to

152
00:13:41,180 --> 00:13:43,080
2 0 to 5.

153
00:13:44,100 --> 00:13:46,140
So I have these two backwards.

154
00:13:46,140 --> 00:13:49,800
And if we look at our graph here.

155
00:13:52,690 --> 00:13:53,590
0 to 5?

156
00:13:53,590 --> 00:13:54,480
That is correct.

157
00:13:54,490 --> 00:13:55,510
1 to 2?

158
00:13:55,540 --> 00:13:56,690
That is correct.

159
00:13:56,710 --> 00:13:57,850
2 to 3?

160
00:13:57,880 --> 00:13:59,170
That is correct.

161
00:14:01,260 --> 00:14:02,790
4 to 5.

162
00:14:02,820 --> 00:14:04,200
That is correct.

163
00:14:04,560 --> 00:14:05,910
And 0 to 1.

164
00:14:05,910 --> 00:14:09,300
So I just had these two in reversed order.

165
00:14:10,350 --> 00:14:17,460
So let me fix that real quick and then we will do this by hand just to verify that this is correct.

166
00:14:18,240 --> 00:14:20,440
Clear cargo test.

167
00:14:20,460 --> 00:14:23,040
So now our test is pass.

168
00:14:24,130 --> 00:14:26,500
So if we look at.

169
00:14:28,090 --> 00:14:30,220
Our output of.

170
00:14:32,130 --> 00:14:37,200
And we will draw this very slowly so that we can see everything.

171
00:14:40,680 --> 00:14:49,690
So we have zero one, two, three, four and five.

172
00:14:49,710 --> 00:14:54,930
We're going from 0 to 5 one 1 to 2.

173
00:14:56,100 --> 00:15:00,960
That is one, 2 to 3 two.

174
00:15:03,050 --> 00:15:04,460
4 to 5.

175
00:15:05,990 --> 00:15:12,260
That is also two and 0 to 1, and that is three.

176
00:15:12,260 --> 00:15:20,660
So as you can tell what we have here and our vector, it is returning our values with the least amount

177
00:15:20,660 --> 00:15:23,000
of weighted edges first.

178
00:15:23,000 --> 00:15:31,100
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,

179
00:15:31,100 --> 00:15:32,120
4 to 5.

180
00:15:32,120 --> 00:15:34,640
And then lastly, 0 to 1 is weight three.

181
00:15:34,640 --> 00:15:40,850
So we have a one, two, three, four, five, six, seven, eight, nine weights.

182
00:15:43,790 --> 00:15:51,050
Well, we see that we have a slightly different output than what we did in the previous lecture where

183
00:15:51,050 --> 00:15:55,400
we went from 2 to 4 instead of 0 to 1.

184
00:15:56,300 --> 00:15:58,250
But if you look, the output is the same.

185
00:15:58,250 --> 00:16:06,560
So we had two minimum spanning trees that we could have used from here, and our union fine algorithm

186
00:16:06,560 --> 00:16:15,920
just went with 0 to 1 because it appears that these nodes came first in the tree, meaning that the

187
00:16:15,920 --> 00:16:18,140
nodes values were compared.

188
00:16:18,140 --> 00:16:22,100
So we have 0 to 1 and those were less than 2 to 4.

189
00:16:22,100 --> 00:16:25,220
So it just arbitrarily picked 0 to 1.

190
00:16:25,970 --> 00:16:32,540
But what we're able to see is that our minimum spanning tree did in fact work and we were successfully

191
00:16:32,540 --> 00:16:39,800
able to create a minimum spanning tree with a weight of nine, which is what we concluded our minimum

192
00:16:39,800 --> 00:16:42,560
spanning tree should have in the previous lecture.

193
00:16:42,650 --> 00:16:49,160
So if you have any questions about this lecture, please feel free to ask me in the Q&A section and

194
00:16:49,160 --> 00:16:53,450
I will see you in the next lecture when we start talking about primes algorithm.