1
00:00:05,820 --> 00:00:10,410
In this lecture, we are going to begin discussing primes algorithm.

2
00:00:10,860 --> 00:00:16,440
And the last lecture we went over an implementation for crew schools algorithm for a minimum spanning

3
00:00:16,470 --> 00:00:22,680
tree and primes is very similar to CRU schools.

4
00:00:23,190 --> 00:00:32,370
It's going to help us find a minimum spanning tree and Primes is going to start at a single node and

5
00:00:32,370 --> 00:00:38,940
then it's going to move through the several several adjacent nodes in order to explore all of the connected

6
00:00:38,940 --> 00:00:40,500
edges along the way.

7
00:00:40,950 --> 00:00:43,950
And that's the general premise to how primes works.

8
00:00:43,950 --> 00:00:52,980
So what we can do is we can create ourself a little graph and we'll say we have Node zero, node one,

9
00:00:53,820 --> 00:01:02,850
two, three and four, and now we can draw all of our edges.

10
00:01:07,350 --> 00:01:09,110
It was provide them weights.

11
00:01:09,120 --> 00:01:18,150
So we have three, four, one six, three, five and two.

12
00:01:20,250 --> 00:01:31,260
So what we can do is we can say our minimum spanning tree visited or vertex excuse me, parent node

13
00:01:32,520 --> 00:01:35,400
and then the weight.

14
00:01:35,790 --> 00:01:41,150
So we know that we're starting out at well, we're going to start out at vertex zero.

15
00:01:41,160 --> 00:01:42,540
So this will be our start.

16
00:01:42,630 --> 00:01:47,520
We don't have a parent and there's no weight given that this is our starting vertex.

17
00:01:48,060 --> 00:01:54,990
So from vertex zero, we will look at all of the neighbors, vertex zero, and we see that we have one

18
00:01:54,990 --> 00:01:55,740
and two.

19
00:01:56,010 --> 00:01:59,930
Two has a weight of four and one has a weight of three.

20
00:01:59,940 --> 00:02:07,680
So for vertex one, we will say the parent is zero and the weight is three.

21
00:02:08,820 --> 00:02:19,920
So we can have our visited section over here and we've currently visited zero and one from one.

22
00:02:20,400 --> 00:02:30,030
Our neighbors are four and two and we see that two has a weight of one.

23
00:02:30,030 --> 00:02:34,860
So for vertex two we say the parent is one and the weight is one.

24
00:02:38,980 --> 00:02:41,350
And then we have vertex three and four.

25
00:02:41,590 --> 00:02:52,060
So from vertex two and let's add it in here for vertex two, we can get to zero one, four and three.

26
00:02:52,090 --> 00:02:57,160
Well, we already know that we have visited one and zero, so we don't have to worry about those.

27
00:02:57,160 --> 00:03:04,450
So all we have to worry about now is two or four and three and we see three has a weight of five, and

28
00:03:04,450 --> 00:03:06,670
four has a weight of three.

29
00:03:07,030 --> 00:03:14,200
So the parent to vertex four will be two and the weight will be three.

30
00:03:15,580 --> 00:03:22,960
And now at four we see that we can get to one, two and three, but we have already visited one and

31
00:03:22,960 --> 00:03:23,560
two.

32
00:03:25,700 --> 00:03:29,420
So the last vertex for us to go to is three.

33
00:03:29,420 --> 00:03:35,090
So we can just go ahead and assume our parent is four and our weight is two.

34
00:03:37,280 --> 00:03:41,540
And now we have a minimum spanning tree that looks something like this.

35
00:03:41,540 --> 00:03:52,640
So we go from 0 to 1 down to 2 to 4 and down to three.

36
00:03:52,970 --> 00:03:57,680
And this is what our minimum spanning tree looks like in the solution.

37
00:03:58,730 --> 00:04:06,410
So now in the next lecture we will begin implementing in premise algorithm, and then we will use this

38
00:04:06,410 --> 00:04:15,410
graph as our test case to ensure that this is the output that we are able to deduce during our test.

39
00:04:15,410 --> 00:04:20,630
So I'll see you in the next lecture when we begin implementing in premise algorithm.