1 00:00:06,070 --> 00:00:10,870 In this lecture we are going to begin implementing in params algorithm. 2 00:00:12,220 --> 00:00:17,710 We are still in section 27 and I just went ahead and commented out all the code from. 3 00:00:18,490 --> 00:00:22,120 Previous implementation of the minimum spanning tree. 4 00:00:22,570 --> 00:00:27,130 That way it's just out of the way and we know that there's not going to be any conflicting code. 5 00:00:28,150 --> 00:00:32,530 So to begin this implementation, we need to bring a couple of items into scope. 6 00:00:32,530 --> 00:00:36,790 The first one is reverse, which I will explain when we get to there. 7 00:00:36,790 --> 00:00:45,790 And the next one is going to be our B tree map and our binary heap collections. 8 00:00:47,110 --> 00:00:54,580 So a lot of this should look really familiar to you because we have implemented most of this before 9 00:00:54,580 --> 00:00:55,330 already. 10 00:00:55,960 --> 00:01:01,060 So I'm just going to quickly go through setting it up that way. 11 00:01:02,400 --> 00:01:05,130 We don't waste too much time going over it. 12 00:01:06,360 --> 00:01:07,360 So we get our graph. 13 00:01:07,380 --> 00:01:14,340 Now we need to add in our adding, creating our edge, and our vertex is going to again implement, 14 00:01:14,340 --> 00:01:21,300 ordered and copy as well as our edge board and copy. 15 00:01:22,680 --> 00:01:26,700 And here we're going to pass in our graph that we want to add the edge to. 16 00:01:28,200 --> 00:01:33,860 It's going to be a mutable graph with our vertex and our edge generics. 17 00:01:33,870 --> 00:01:43,470 We have vertex one, which is a Type V, our vertex two, and then we have our weight, which is our 18 00:01:43,470 --> 00:01:44,070 edge. 19 00:01:46,110 --> 00:01:52,470 And since this is an undirected graph, what we are going to do is go from vertex one to vertex two 20 00:01:52,470 --> 00:01:54,960 and from vertex two to vertex one. 21 00:01:55,230 --> 00:02:07,830 So we want to call or end cert width and we're going to have a B tree map new which calls insert, which 22 00:02:07,830 --> 00:02:11,970 calls value to with weight. 23 00:02:13,120 --> 00:02:19,870 And we can copy and paste this and again, reverse from vertex one to vertex two. 24 00:02:21,190 --> 00:02:25,750 So our add edge function looks good now. 25 00:02:25,750 --> 00:02:32,530 So now we can add in our print implementation where we're going to have our vertex implementing and 26 00:02:32,530 --> 00:02:36,340 ORD and copy as well as our edge. 27 00:02:40,960 --> 00:02:49,030 And we're going to pass in a graph which is going to be a reference to a graph and we need our starting 28 00:02:49,030 --> 00:02:50,080 vertex 29 00:02:53,500 --> 00:02:55,360 and so that we have something to compare against. 30 00:02:55,360 --> 00:03:02,110 We are going to return a graph that way we have a graph to test against. 31 00:03:03,370 --> 00:03:12,850 So now we're going to create a new mutable variable called MST, which is going to be a new graph and 32 00:03:12,850 --> 00:03:18,940 we want to return our minimum spanning tree so we can go ahead and do that and we want to keep track 33 00:03:18,940 --> 00:03:21,220 of who we have visited. 34 00:03:22,330 --> 00:03:33,790 So we will say binary heap new and now we want to insert into our minimum spanning tree our starting 35 00:03:33,790 --> 00:03:38,560 value and put in a new B tree map. 36 00:03:43,300 --> 00:03:43,840 All right. 37 00:03:45,250 --> 00:03:52,240 So now that we have inserted in our starting vertex into our minimum spanning tree, we now need to 38 00:03:52,240 --> 00:04:07,930 get all of our neighbors so we can say for vertex with weight in our graph start, we want to push these 39 00:04:07,930 --> 00:04:15,730 into visited and we're going to push them in and reverse order, which I will explain why in a second. 40 00:04:15,730 --> 00:04:16,230 Let me. 41 00:04:17,680 --> 00:04:18,250 All right. 42 00:04:18,370 --> 00:04:23,950 So we push in and we need to pass this in by reference. 43 00:04:23,950 --> 00:04:24,490 There we go. 44 00:04:26,140 --> 00:04:32,710 So if we look at the binary heap, we say we see that it says this is going to be a max heap. 45 00:04:33,550 --> 00:04:39,880 What reverse is going to allow us to do is it's going to allow us to take this max heap implementation 46 00:04:39,880 --> 00:04:43,360 and turn it into a minimum heap. 47 00:04:43,870 --> 00:04:54,460 And this is important because it will allow us to put all of our edges with a minimum weight first into 48 00:04:54,460 --> 00:04:56,380 our minimum heap. 49 00:04:56,380 --> 00:05:04,720 And if you remember from the previous lecture that that will be beneficial because we want to add all 50 00:05:04,720 --> 00:05:08,800 the minimum edges into our minimum spanning tree first. 51 00:05:09,880 --> 00:05:18,100 So what we can do now, and this will help tie it all together, is while we say let some and then we 52 00:05:18,100 --> 00:05:33,430 need to reverse it, I'll let some weight and we'll say v, t and pre equals visited dot pop and this 53 00:05:33,430 --> 00:05:37,270 is where it matters that we turned it into a minimum heap. 54 00:05:37,270 --> 00:05:44,590 That way when we pop off of our minimum heap, we are getting the vertex with the edge of the minimum 55 00:05:44,590 --> 00:05:49,900 weight because that's what we want to check to see if it's already in the minimum spanning tree. 56 00:05:49,900 --> 00:05:54,910 So if it is, we can say we need to check if it's in the minimum spanning tree. 57 00:05:54,910 --> 00:05:59,410 So if that vertex is in the minimum spanning tree, then continue. 58 00:05:59,410 --> 00:06:03,220 That way we can get to the next value that we want to pop off. 59 00:06:04,390 --> 00:06:11,920 That way we're continuously trying to make sure that we have the minimum edge being added into our minimum 60 00:06:11,920 --> 00:06:17,230 spanning tree, because if it was not already in our minimum spanning tree, well now we're going to 61 00:06:17,230 --> 00:06:28,360 add it into our minimum spanning tree by saying add in our previous, connect it to our vertex and pass 62 00:06:28,360 --> 00:06:29,620 in the weight. 63 00:06:31,450 --> 00:06:39,640 And once we add it in, well, now we need to get all the neighbors for that new vertex so we can say 64 00:06:39,640 --> 00:06:49,630 for vertex weight in a reference to our graph and our vertex that we are now at. 65 00:06:53,050 --> 00:07:02,410 If the minimum spanning tree does not contain the the key of a neighboring vortex vertex, then we want 66 00:07:02,410 --> 00:07:06,910 to say visited dot push and again reverse. 67 00:07:06,910 --> 00:07:15,730 That way we know that it's being added in properly of that weight, that vertex that we are our neighbor 68 00:07:15,730 --> 00:07:23,530 is at and then our parent vertex and that's all we have to do. 69 00:07:23,530 --> 00:07:30,490 So we are successfully looking at all the adjacent neighbors getting their minimum edges and then adding 70 00:07:30,490 --> 00:07:36,760 them into the minimum spanning tree, moving to that new edge that we just added into the minimum spanning 71 00:07:36,760 --> 00:07:41,440 tree, getting all of their edges and performing the same logic. 72 00:07:43,000 --> 00:07:45,550 So our implementation looks pretty sound. 73 00:07:45,550 --> 00:07:55,690 So we can now test this out and we will say config test, mod test. 74 00:07:57,770 --> 00:07:59,870 Use super. 75 00:08:01,730 --> 00:08:06,020 And now we can create our test of testing our frames algorithm. 76 00:08:08,060 --> 00:08:11,830 F in test primes. 77 00:08:13,910 --> 00:08:16,810 So what we need to do is create our graph. 78 00:08:16,820 --> 00:08:23,210 So we will say let graph equals B tree map new. 79 00:08:23,540 --> 00:08:26,090 And now we know that we need to add some edges. 80 00:08:26,090 --> 00:08:36,320 So we will say add an edge to our mutable graph, start a vertex zero, go to one and our weight of 81 00:08:36,320 --> 00:08:36,860 three. 82 00:08:37,160 --> 00:08:40,730 So we are going to create the graph that we did in the previous lecture. 83 00:08:40,730 --> 00:08:44,990 So we know we have seven edges three, four, five, six, seven. 84 00:08:45,380 --> 00:08:48,080 We go from 0 to 1 with the weight of three. 85 00:08:49,040 --> 00:08:52,550 We go from 0 to 2 with a weight of four. 86 00:08:53,060 --> 00:08:56,210 We go from 1 to 2 with a weight of one. 87 00:08:58,980 --> 00:09:04,710 To go from 1 to 4 with a weight of six. 88 00:09:05,670 --> 00:09:09,090 We go from 2 to 4 with the weight of three. 89 00:09:09,420 --> 00:09:20,550 We go from 2 to 3 with the weight of five, and we go from 3 to 4 with a weight of two. 90 00:09:21,780 --> 00:09:34,230 So that graph is set up successfully and now we need to create an answer graph to compare our return 91 00:09:34,230 --> 00:09:35,100 value to. 92 00:09:36,780 --> 00:09:38,970 So we will create another new tree map. 93 00:09:38,970 --> 00:09:41,850 We know we have four edges here. 94 00:09:42,330 --> 00:09:44,280 We need to change the name of this. 95 00:09:46,610 --> 00:09:49,400 Change the name of this graph to ants. 96 00:09:50,660 --> 00:09:52,610 And we know that we go from 0 to 1. 97 00:09:52,610 --> 00:09:57,200 With three, we go from 1 to 2 with a weight of one. 98 00:09:59,810 --> 00:10:01,520 We go from 2 to 4 99 00:10:04,580 --> 00:10:10,640 with a weight of three, and we go from 4 to 3 with the weight of two. 100 00:10:12,720 --> 00:10:16,500 4 to 3 with a weight of two. 101 00:10:18,420 --> 00:10:33,180 And now we need to assert equals that are prim and graph with a starting vertex of zero is equal to 102 00:10:33,180 --> 00:10:34,500 our answer graph here. 103 00:10:34,500 --> 00:10:40,950 And again, this graph is what we did in the previous lecture, and this was the solution we also found 104 00:10:40,950 --> 00:10:48,930 in the previous lecture so we can run cargo test and we see that our test runs successfully. 105 00:10:48,930 --> 00:10:52,950 So we know that our PARAMS algorithm is successfully running. 106 00:10:52,950 --> 00:10:58,620 So I hope you enjoyed this lecture on primes algorithms implementation. 107 00:10:58,620 --> 00:11:05,310 If you have any questions about anything that we did or on anything regarding primes algorithm or any 108 00:11:05,310 --> 00:11:11,880 other minimum spanning tree that we did in this section, please feel free to ask me in the Q&A section.