1 00:00:01,060 --> 00:00:08,110 OK, so now that we have talked a decent amount about depth, first search, we are going to get into 2 00:00:08,500 --> 00:00:14,500 the other algorithm that I believe I casually mentioned in the first death research lecture for a second, 3 00:00:14,500 --> 00:00:16,090 which is breath for a search. 4 00:00:16,240 --> 00:00:18,040 So let's get right into it. 5 00:00:18,850 --> 00:00:24,730 So breath first search BFFs for short is different from death for search. 6 00:00:24,730 --> 00:00:30,340 And in that instead of us like, let's say we start at some note here instead of us going deep. 7 00:00:30,760 --> 00:00:37,600 First, we want to explore all the possible nodes that are nearby, neighboring adjacent nodes first. 8 00:00:37,930 --> 00:00:40,210 And we kind of explore in layers like that. 9 00:00:40,960 --> 00:00:47,110 So rather than us like taking a path all the way down, we are going to explore every adjacent node, 10 00:00:47,110 --> 00:00:51,010 every neighboring node for a given node vertex. 11 00:00:52,990 --> 00:00:56,740 So let's go ahead and just do a simple walk through it. 12 00:00:56,740 --> 00:00:59,350 And I'm not going over the algorithm in detail right now. 13 00:00:59,350 --> 00:01:04,180 I'm just showing what order the nodes would be vested in so you can pick any starting point. 14 00:01:04,570 --> 00:01:09,460 But I think this is a similar graph to what we did in depth research, and I'm just going to start here, 15 00:01:09,460 --> 00:01:12,880 probably how I did four death research, two, which is at this node. 16 00:01:12,880 --> 00:01:13,270 See? 17 00:01:14,480 --> 00:01:17,030 So let's go ahead and start there. 18 00:01:17,390 --> 00:01:23,210 So we start to see I'm going to label the order so from see and I'm just going to choose to go. 19 00:01:23,390 --> 00:01:24,980 I got to go to all of its neighbors. 20 00:01:24,980 --> 00:01:27,230 So aid and efforts neighbors, right? 21 00:01:27,680 --> 00:01:29,000 I'm just going to use a first. 22 00:01:29,570 --> 00:01:35,090 So I go to a and then I'm going to choose the and then f. 23 00:01:35,300 --> 00:01:40,520 So I visited all of its neighbors since he was number one, and we can go to number two now and I'm 24 00:01:40,520 --> 00:01:41,330 going to explore that. 25 00:01:42,230 --> 00:01:48,040 So its neighbors are B and C, but we've already explored C. 26 00:01:48,050 --> 00:01:49,040 It's already visited. 27 00:01:49,490 --> 00:01:54,320 So I am not going to consider that I'm just going to go here. 28 00:01:55,130 --> 00:01:56,510 So that would be the fifth node. 29 00:01:56,960 --> 00:02:02,750 And when something is already visited, that's an important thing to note, and I'm going to do a more 30 00:02:02,750 --> 00:02:08,780 detailed walkthrough in the next slide, and I'm going to kind of be redundantly adding the visited 31 00:02:08,780 --> 00:02:15,440 node so you can see, like how many things would actually be considered if we weren't kind of filtering 32 00:02:15,440 --> 00:02:17,090 out the things we've already visited. 33 00:02:17,490 --> 00:02:18,890 But in this example, we're not doing that. 34 00:02:18,890 --> 00:02:21,590 We're just doing a simple walkthrough and ignoring what we visited. 35 00:02:21,590 --> 00:02:23,750 So let's continue on. 36 00:02:25,580 --> 00:02:33,180 So we explored a and this was its only new neighbor that we hadn't visited. 37 00:02:33,200 --> 00:02:37,210 So now we're going to go from two to three, so let's look at Dee Dee. 38 00:02:37,260 --> 00:02:40,400 We already have visited all of its neighbors. 39 00:02:42,340 --> 00:02:53,410 So let's go ahead on to F if we haven't visited G so well, that's a G, then let's we were f. 40 00:02:53,410 --> 00:02:54,190 That's for now. 41 00:02:54,190 --> 00:02:54,920 We got to be. 42 00:02:54,940 --> 00:02:55,720 So it's five. 43 00:02:55,810 --> 00:02:57,070 What about these neighbors? 44 00:02:57,080 --> 00:03:01,600 The ones we haven't seen are J H and E, so we do those three. 45 00:03:02,950 --> 00:03:10,790 Between those three and we were at five for me now, we are six from Gee, we haven't seen, I see. 46 00:03:11,120 --> 00:03:13,370 So we go to I at that. 47 00:03:14,380 --> 00:03:19,670 And yet you notice that all of our nodes are visited now. 48 00:03:20,140 --> 00:03:26,830 Of course, when we, you know, we went out and checked out, I mean, we would if we were six year, 49 00:03:26,830 --> 00:03:28,300 we would want to go to seven. 50 00:03:28,300 --> 00:03:32,740 You know, notice has no new neighbors, a notice that has no new neighbors. 51 00:03:32,890 --> 00:03:35,300 I notice astounded neighbors and explore I. 52 00:03:35,500 --> 00:03:35,800 But. 53 00:03:36,790 --> 00:03:41,470 Everything is highlighted in our graph now, so are good to go. 54 00:03:42,700 --> 00:03:46,450 So I made the graph a little smaller because it gets. 55 00:03:47,510 --> 00:03:51,680 Really big with how many times we're checking out neighboring nodes. 56 00:03:52,220 --> 00:03:59,210 If I don't do that, so now I'm going to go through this in more detail and talk more about the algorithm. 57 00:03:59,210 --> 00:04:06,350 So if you think back to depth first search, you probably remember that we were using a stack to kind 58 00:04:06,350 --> 00:04:10,040 of keep track of where we were and where we came from and all that. 59 00:04:10,040 --> 00:04:15,830 And that's what gave us the death for search ordering really was being able to use that stat. 60 00:04:16,790 --> 00:04:22,460 So that was a last in first out data structure. 61 00:04:22,850 --> 00:04:27,380 And you remember the other one we talked about, which is the opposite, is a first in, first out data 62 00:04:27,380 --> 00:04:28,880 structure, which is a queue. 63 00:04:29,240 --> 00:04:34,850 So unlike death for search with the stack, we are going to be using a Q for breath for search. 64 00:04:35,330 --> 00:04:36,800 So let's see how that would work. 65 00:04:36,830 --> 00:04:40,490 I'm going to go ahead and start right here on the same node. 66 00:04:40,490 --> 00:04:47,480 See, but it's a smaller graph and I have my Q kind of going here as I add and pop from it, and it 67 00:04:47,480 --> 00:04:49,790 might need some additional space. 68 00:04:50,330 --> 00:04:52,520 I can't remember if it overflows or not. 69 00:04:53,180 --> 00:04:57,050 But let's get right into it and I will go over all the steps of the algorithm here. 70 00:04:58,430 --> 00:05:02,870 So right off the bat, what we're going to do is push our starting node to the queue. 71 00:05:03,080 --> 00:05:06,590 So we're going to do a push back on on the queue of our starting node. 72 00:05:06,590 --> 00:05:14,000 And that is see then the next thing we want to do in this kind of is where our loop would start. 73 00:05:14,110 --> 00:05:18,620 An iterative solution is we we would start a loop. 74 00:05:18,620 --> 00:05:23,750 And the first thing we do inside that loop is get the first thing out of the queue. 75 00:05:23,750 --> 00:05:24,710 So the front item. 76 00:05:26,000 --> 00:05:32,260 So we get that out and that see and then after we get that from one out, then we would pop it off. 77 00:05:32,270 --> 00:05:36,740 So imagine what just kind of popping it into a variable. 78 00:05:38,330 --> 00:05:39,020 So we pop off. 79 00:05:39,020 --> 00:05:43,880 See, and now that we have see, we're going to process and visit see. 80 00:05:44,720 --> 00:05:49,900 And so I put this year and then we are going to check out its neighbors. 81 00:05:50,270 --> 00:05:52,470 So what are these neighbors? 82 00:05:52,490 --> 00:05:54,050 They're a D and F. 83 00:05:54,950 --> 00:05:56,480 What are we going to do for those neighbors? 84 00:05:56,510 --> 00:06:01,160 Well, we're going to add them all to the queue, so we add a d in to the queue. 85 00:06:03,700 --> 00:06:11,380 After that, we just go back up to the top of the loop, so let's go back up and do the same thing. 86 00:06:11,860 --> 00:06:13,480 So what is the first thing in the queue? 87 00:06:13,490 --> 00:06:18,460 Because we thought that the first thing in the queue is a soda pop that out and get a. 88 00:06:19,720 --> 00:06:22,630 Now this isn't a process, eh? 89 00:06:22,780 --> 00:06:26,920 And then let's ask what are A's neighbors? 90 00:06:27,340 --> 00:06:31,390 So A's neighbors are B and C. 91 00:06:32,080 --> 00:06:37,660 And one thing that I'm doing is also checking, if you remember back to death for search, we had to 92 00:06:37,660 --> 00:06:46,720 have that visited map where we would change anything that wasn't visited to a one when we visited it 93 00:06:46,740 --> 00:06:51,520 and we checked to see if there's a zero or one there to know if it had been visited yet. 94 00:06:51,940 --> 00:06:53,290 We're doing the same thing here. 95 00:06:53,890 --> 00:06:56,050 So if a. 96 00:06:57,190 --> 00:07:02,350 Was already like having this yellow ring that I wouldn't have visited it, so I'm going to ask that 97 00:07:02,350 --> 00:07:07,270 each time actually before processing it, so we'll probably have a queue and then part of what we need 98 00:07:07,270 --> 00:07:14,770 to do is ask, Hey, is this thing visited yet or not, if it's not visited and let's go visit it and 99 00:07:14,770 --> 00:07:15,370 process it? 100 00:07:15,370 --> 00:07:17,950 So that's another part to keep in mind. 101 00:07:19,290 --> 00:07:27,480 So we're on a and A has C and B as neighbors, and normally what you would also want to do is check 102 00:07:27,480 --> 00:07:33,230 the visited for the sorry check, whether the neighbors were visited already. 103 00:07:33,240 --> 00:07:35,610 So you don't want to add the ones that are visited. 104 00:07:36,000 --> 00:07:41,910 But just to show you kind of how much it adds up, I'm going to just add it to the queue anyways. 105 00:07:42,900 --> 00:07:44,790 So it would still work out. 106 00:07:45,150 --> 00:07:48,000 But it would be better not to add that stuff. 107 00:07:48,390 --> 00:07:58,200 So I add CMB, although in our studio code, in the next slide, we will just be adding B because we're 108 00:07:58,200 --> 00:08:00,660 going to make that check to see if it's visited. 109 00:08:02,310 --> 00:08:09,990 So next thing, let's pull out of the queue and we're going to go visit because it's not visited, you 110 00:08:09,990 --> 00:08:11,610 know, it doesn't have the yellow ring on it yet. 111 00:08:12,120 --> 00:08:18,000 So let's go ahead and visit it and that having the yellow ring once again is kind of corresponding to 112 00:08:18,060 --> 00:08:19,120 the map. 113 00:08:19,140 --> 00:08:21,860 It has a zero or a one four visited or not. 114 00:08:21,900 --> 00:08:22,110 Four. 115 00:08:23,760 --> 00:08:25,230 So what are these neighbors? 116 00:08:25,260 --> 00:08:28,290 Well, we have a CB and F. So I add all this. 117 00:08:30,420 --> 00:08:31,560 Then I pull out if. 118 00:08:33,430 --> 00:08:35,680 Visit F, because it's not visited yet. 119 00:08:36,730 --> 00:08:37,720 What are its neighbors? 120 00:08:38,950 --> 00:08:44,770 So those get at it, and I know I've mentioned it several times already, but we would not add the visited 121 00:08:44,770 --> 00:08:45,640 nodes actually. 122 00:08:45,640 --> 00:08:49,780 When we're implementing it, I'm just doing it here to show you how much the Q really builds up if you 123 00:08:49,780 --> 00:08:50,170 do that. 124 00:08:52,400 --> 00:08:58,650 So now we have see and we see out well, we've already visited everything for CES. 125 00:08:58,730 --> 00:09:00,590 You can see that redundancy there. 126 00:09:01,430 --> 00:09:04,790 So we don't do anything be haven't visited. 127 00:09:05,160 --> 00:09:10,490 So let's face it being, we process B B has a and a d. 128 00:09:10,490 --> 00:09:10,910 Sorry. 129 00:09:11,120 --> 00:09:12,350 So we have A. J. 130 00:09:13,550 --> 00:09:17,240 And now we're going to pop out, she's already been visited. 131 00:09:17,270 --> 00:09:21,380 We're doing the same thing again, so you can see how this is becoming really redundant. 132 00:09:22,640 --> 00:09:26,900 So be we've already visited that f we've already visited that. 133 00:09:28,370 --> 00:09:30,410 She already visited that. 134 00:09:30,410 --> 00:09:35,150 Of course, now we've had multiple season here, d already visited that. 135 00:09:35,960 --> 00:09:40,790 Gee, we have not visited, so we will go ahead and visit and process G. 136 00:09:41,420 --> 00:09:46,490 And F. Although, like I said, this is redundant. 137 00:09:48,630 --> 00:09:55,740 A report about a and that's been visited, of course, has been visited, GE has, and so we will. 138 00:09:56,130 --> 00:10:03,360 It's a J J Neighbours B redundantly push B and then F. 139 00:10:04,110 --> 00:10:07,710 We have seen F and B out. 140 00:10:07,740 --> 00:10:08,610 We've seen B. 141 00:10:09,420 --> 00:10:11,280 You noticed there was a lot of redundancy here. 142 00:10:11,280 --> 00:10:17,370 So that is why we are going to also make B check with the F inside of the lubed. 143 00:10:17,370 --> 00:10:19,140 It looks for our neighbors as well. 144 00:10:19,410 --> 00:10:23,640 So when we're adding neighbours to the queue, looping over all the neighbours of a given node, we 145 00:10:23,640 --> 00:10:26,520 are going to only add it if it hasn't been visited. 146 00:10:28,310 --> 00:10:35,300 So now this tells you that you are done, actually, because once the queue is empty, we are done, 147 00:10:35,300 --> 00:10:37,520 we would go back up for a one one iteration. 148 00:10:38,840 --> 00:10:45,800 And we would see that the queue is empty and the main outer loop of this would stop. 149 00:10:46,250 --> 00:10:48,770 And that's when we know breadth first search has finished. 150 00:10:49,910 --> 00:10:51,710 So let's take a look at the pseudocode. 151 00:10:53,100 --> 00:10:57,810 So we start up here with the definition, we get these starting vortex parts to it. 152 00:10:58,590 --> 00:11:04,830 And the first thing we did, just like when we push back, see and hear right away as we push back that 153 00:11:04,830 --> 00:11:09,150 starting vertex, then we have this loop while the queue is not empty. 154 00:11:10,350 --> 00:11:13,320 And while the queue is not empty, we're going to do all this in here. 155 00:11:14,190 --> 00:11:20,850 The first thing we do is we grab the front thing from the queue and there's two things that should happen 156 00:11:20,850 --> 00:11:21,090 here. 157 00:11:21,090 --> 00:11:26,100 I didn't really put pop, but you should also be popping. 158 00:11:26,100 --> 00:11:31,650 So remember when we grab the first thing from the front, we're also like popping it off so you can 159 00:11:31,650 --> 00:11:37,590 think of it as like two steps or one step, but we need to reference the front. 160 00:11:37,890 --> 00:11:42,690 And then after that, we would want to perform a pop on the queue to get rid of the front item. 161 00:11:43,830 --> 00:11:48,750 Then we say if that thing that we just popped into this variable from the front, if it's not visited 162 00:11:48,990 --> 00:11:50,280 Vertex, it's not visited. 163 00:11:50,550 --> 00:11:56,070 Then let's go ahead and add it to visited, which is changing the zero to the one in the correct position 164 00:11:56,400 --> 00:11:57,630 of the visited map. 165 00:11:59,100 --> 00:12:03,960 Then we are going to process it, and this can be whatever, but we're just going to print it out for 166 00:12:03,960 --> 00:12:04,710 simplicity. 167 00:12:06,470 --> 00:12:13,430 At that point, we want to go through all of the neighbors of the current vertex where it so we go through 168 00:12:13,430 --> 00:12:17,690 all of its neighbors and this is what I'm talking about to eliminate that redundancy. 169 00:12:18,140 --> 00:12:24,740 We want to say if the neighbor is not visited, then we'll push it back to the queue. 170 00:12:25,070 --> 00:12:27,890 Otherwise, we will not push it back to the queue. 171 00:12:29,210 --> 00:12:30,500 And so that's pretty much it. 172 00:12:30,750 --> 00:12:35,360 You know, just remember that I said we also hear it's not mentioned here, but I assume that you should 173 00:12:35,360 --> 00:12:37,310 also pop off. 174 00:12:38,150 --> 00:12:39,140 From the queue right here. 175 00:12:39,560 --> 00:12:42,560 So you would get the thing from the front of the queue and pop it off the queue. 176 00:12:45,390 --> 00:12:50,970 OK, so let's go ahead and recap as well on the time complexity. 177 00:12:51,000 --> 00:12:57,240 So one thing now that we're kind of wrapping this up with the debt research and breath research, and 178 00:12:57,240 --> 00:12:59,640 we'll go into the code of it in the next lecture. 179 00:13:00,690 --> 00:13:06,510 Just briefly, but the time complexity is pretty much dependent for both of these algorithms, it's 180 00:13:06,510 --> 00:13:08,700 dependent on the way that you implement the graph. 181 00:13:08,850 --> 00:13:14,190 So remember, we had two things that we talked about in adjacency list or an adjacency matrix. 182 00:13:15,060 --> 00:13:20,970 So really, what you want to be thinking about is the fact that the adjacency list is not really going 183 00:13:20,970 --> 00:13:28,410 to yield the time complexity of Bigo of vertices plus edges and then the adjacency matrix. 184 00:13:28,410 --> 00:13:36,960 Since we have a grid that is, you know, in vertices by and vertices that end by in dimension and you 185 00:13:36,960 --> 00:13:43,730 have to go over all of the columns for all the rows that makes you have a time complexity of Bigo of 186 00:13:43,740 --> 00:13:44,670 vertices squared. 187 00:13:46,130 --> 00:13:52,790 So important things to think about when you are considering the time complexity of these algorithms. 188 00:13:53,600 --> 00:14:01,490 So with that, I think that we're probably good to go and can head over to the code. 189 00:14:01,500 --> 00:14:07,550 So I will see you in the next lecture where we will go over the implementation of the Code for Breath 190 00:14:07,570 --> 00:14:08,090 Research.