1 00:00:06,960 --> 00:00:12,390 In this lecture, we are going to implement the algorithm breadth first search. 2 00:00:13,140 --> 00:00:18,480 Now, this implementation is going to be pretty similar to depth for search. 3 00:00:18,870 --> 00:00:27,570 But instead of our algorithm going all the way to the end of the graph, we want to fan out and hit 4 00:00:27,570 --> 00:00:30,360 all our neighbors at that current depth. 5 00:00:31,560 --> 00:00:37,710 So let's see what this would look like so we can say pub f in breath. 6 00:00:39,420 --> 00:00:45,540 First search we want to pass in our graph. 7 00:00:47,460 --> 00:00:55,530 We want our root vertex and we want our target vertex. 8 00:00:56,430 --> 00:01:06,390 And just like in depth first search, we want to pass back or return an option with a vector containing 9 00:01:06,390 --> 00:01:06,700 u. 10 00:01:06,720 --> 00:01:07,380 X. 11 00:01:09,000 --> 00:01:14,770 We want our visited which is going to be a hash. 12 00:01:14,790 --> 00:01:20,850 Set vertex is and we want to create a new one 13 00:01:24,240 --> 00:01:27,570 and we want our history. 14 00:01:35,280 --> 00:01:46,980 And lastly, we need our Q which is going to be a vec dx Q and we need to make our cube mutable. 15 00:01:50,650 --> 00:01:51,070 All right. 16 00:01:51,070 --> 00:01:59,050 So we want to say we've already visited our root node since that is where we are starting out at and 17 00:01:59,050 --> 00:02:09,790 we want to push back our root node and then we can have our Y loop. 18 00:02:09,790 --> 00:02:18,780 So we have our current vertex again and we are going to pop the front of our queue. 19 00:02:20,870 --> 00:02:21,500 All right. 20 00:02:23,210 --> 00:02:33,410 So now we have our history dot push, our current vertex dot value, which we did in depth first. 21 00:02:34,130 --> 00:02:39,230 And then if we reach the current goal, we want to return our travel history. 22 00:02:39,230 --> 00:02:52,700 So if current vertex is equal to our target, return some history. 23 00:02:54,260 --> 00:02:58,640 Otherwise we need to check the neighboring nodes for any that we have not visited yet. 24 00:02:58,640 --> 00:03:07,370 So we can say for neighbor and current vertex neighbors of graph. 25 00:03:13,950 --> 00:03:22,140 If visited does not can obtain our neighbor. 26 00:03:25,100 --> 00:03:28,370 Then visited dot insert 27 00:03:30,350 --> 00:03:31,160 neighbor. 28 00:03:32,950 --> 00:03:34,570 And cue dot. 29 00:03:35,680 --> 00:03:38,350 Push back our neighbor. 30 00:03:38,350 --> 00:03:42,700 That way we're getting all of our neighbors at that current depth. 31 00:03:44,770 --> 00:03:53,110 And then otherwise, if we're we don't ever find our target and all nodes we're already visited, then 32 00:03:53,110 --> 00:03:57,940 we can return none because it is not inside of our graph. 33 00:03:58,390 --> 00:04:05,740 So again, looks very similar to depth first search, but instead of us iterating all the way to the 34 00:04:05,740 --> 00:04:11,890 end, we just look at all the immediate neighbors, visit those, see if it's the value that we're looking 35 00:04:11,890 --> 00:04:12,610 for. 36 00:04:12,640 --> 00:04:21,220 If not, then we can go up one more depth so we can now add in some of our test cases. 37 00:04:21,220 --> 00:04:22,060 And let's. 38 00:04:24,460 --> 00:04:26,950 Keep our test cases the same. 39 00:04:27,490 --> 00:04:34,030 So we'll say test F in and we'll call it breadth First search and we'll call it fail. 40 00:04:34,930 --> 00:04:40,780 And what we can do is actually come up here and we can create. 41 00:04:42,820 --> 00:04:47,200 The same test cases that we were already doing. 42 00:04:48,160 --> 00:04:52,840 So we're looking for a value here that does not exist. 43 00:04:54,460 --> 00:05:00,130 So now we can say assert equals and we can say breadth. 44 00:05:00,130 --> 00:05:11,020 First search, pass in our graph, pass in our route into and pass in our target dot or not target in 45 00:05:11,020 --> 00:05:21,850 this case objective dot into and we want to see that it returns back none. 46 00:05:24,140 --> 00:05:31,580 And then our other test case, we want it to actually find something. 47 00:05:31,580 --> 00:05:41,870 So we will say, take all of this, copy it down and say F and BFS 48 00:05:43,880 --> 00:05:50,660 found copy all this in, we will change our objective to seven. 49 00:05:50,990 --> 00:06:04,070 And in this instance, we will say breadth first search and we can say path here. 50 00:06:04,970 --> 00:06:09,470 And we can say let path equals a VEC. 51 00:06:09,470 --> 00:06:19,960 And we expect our path to be one, two, three, four, five, six and seven because we expect 1 to 52 00:06:19,960 --> 00:06:22,490 1, it's going to connect to two and three. 53 00:06:22,490 --> 00:06:27,890 So we expect 1 to 3 to be visited and then we see two connects to four and five. 54 00:06:27,890 --> 00:06:32,570 So then we expect four and five to be visited and then three connects to six and seven. 55 00:06:32,570 --> 00:06:35,300 So then we expect six and seven to be visited. 56 00:06:35,300 --> 00:06:39,440 So we have one, two, three, four, five, six and seven. 57 00:06:39,620 --> 00:06:42,590 So let's run cargo tests to see how it looks. 58 00:06:42,590 --> 00:06:53,330 And it says we expected an e num option, found our VEC. 59 00:06:54,200 --> 00:06:59,540 We need to put some around our path 60 00:07:02,810 --> 00:07:06,410 and the dreaded forgot semicolon. 61 00:07:07,160 --> 00:07:08,000 There we go. 62 00:07:08,000 --> 00:07:14,750 And we see that breadth first search fail and found both ran successfully so. 63 00:07:16,520 --> 00:07:23,270 Safe to say that our breadth first search algorithm is also successfully implemented in and again, 64 00:07:23,540 --> 00:07:24,890 you might have noticed that. 65 00:07:25,750 --> 00:07:31,450 Breadth of research in depth research are extremely similar, and that is because they are. 66 00:07:31,450 --> 00:07:39,190 So again, the big key takeaway here is that depth first is going to go to the end of the graph and 67 00:07:39,190 --> 00:07:46,660 then it will work its way back to visit any any nodes that it may have missed, whereas breadth first 68 00:07:46,660 --> 00:07:54,730 is going to fan out, meaning it'll get every single vertex at that current depth level before moving 69 00:07:54,730 --> 00:07:55,240 on. 70 00:07:55,480 --> 00:08:01,210 So if you have any questions about depth first search or breadth first search, please feel free to 71 00:08:01,210 --> 00:08:06,670 ask them in the Q&A section and we will look over one more graphing. 72 00:08:07,970 --> 00:08:11,990 Algorithm known as Dijkstra's Shortest Path. 73 00:08:11,990 --> 00:08:15,620 And we will begin talking about that in the next lecture.