1 00:00:00,150 --> 00:00:04,430 OK, so let's get into coding this breath for research. 2 00:00:04,890 --> 00:00:09,000 So pretty much have the same file that I use for death, for search. 3 00:00:09,000 --> 00:00:15,750 I just kind of deleted the dev for a search function and the prototype, and I'm using that same project. 4 00:00:15,750 --> 00:00:19,050 So if you want to do that and use the same project, that's totally fine. 5 00:00:19,050 --> 00:00:23,150 Otherwise, if you want to start from scratch, for some reason, you can go ahead and do that too. 6 00:00:23,160 --> 00:00:28,890 The only thing that I've seen so far is I included a deck, which is the double ending cue that you 7 00:00:28,890 --> 00:00:30,330 might have noticed from the project. 8 00:00:31,260 --> 00:00:33,630 You can use just a standard cue as well. 9 00:00:34,740 --> 00:00:35,150 I don't know. 10 00:00:35,160 --> 00:00:38,280 I use the deck, I just kind of put it in there, so that's what I'm going to use. 11 00:00:38,280 --> 00:00:43,350 But to each his own, if you want, is a cue that's totally fine or whatever Dave structure makes sense 12 00:00:43,350 --> 00:00:43,740 to you. 13 00:00:45,460 --> 00:00:46,700 They can function like a queue. 14 00:00:46,720 --> 00:00:47,170 Of course. 15 00:00:47,650 --> 00:00:55,300 So then since I have that, I should go ahead and add it, so I'm going to add a deck of chairs and 16 00:00:55,300 --> 00:00:57,640 I'm going to call that PFC queue. 17 00:00:58,690 --> 00:01:06,220 Then I'm going to prototype a function just called BFS instead of DFS, which is going to be void. 18 00:01:06,850 --> 00:01:10,740 And I'm going to have the starting Vertex attacks, which will be type char. 19 00:01:12,190 --> 00:01:14,270 So it's just a prototype. 20 00:01:14,290 --> 00:01:18,340 So let's do the actual one implementation. 21 00:01:19,510 --> 00:01:21,430 So what do we have to do for this? 22 00:01:21,730 --> 00:01:23,690 Well, let's think about it. 23 00:01:23,740 --> 00:01:28,090 First off, we said that we had to push the starting Vertex two the queue. 24 00:01:28,240 --> 00:01:29,920 So let's go ahead and do that. 25 00:01:30,460 --> 00:01:37,390 So it'll just be your first queue dot, push back and push back. 26 00:01:39,220 --> 00:01:43,630 Then we're going to start early of where we're going to loop as long as the queue is not empty. 27 00:01:43,630 --> 00:01:48,460 So well, not the first queue empty and we will loop. 28 00:01:49,960 --> 00:01:57,220 Then what we need to do now is let's see. 29 00:01:57,700 --> 00:02:01,620 We need to get the first thing off the front of the queue, right? 30 00:02:01,630 --> 00:02:08,940 So we're going to do childcare equals the VFX of the office. 31 00:02:08,980 --> 00:02:14,800 Q Scott front and remember that we also need to pop. 32 00:02:15,040 --> 00:02:21,460 So I'm going to also be your first Q Dot pop front. 33 00:02:23,770 --> 00:02:27,610 So, yeah, now we're pushing back and popping for front. 34 00:02:29,320 --> 00:02:35,320 And so what we do now is we're going to do a check to see if it's visited the country that we just made 35 00:02:36,160 --> 00:02:36,650 the career. 36 00:02:36,650 --> 00:02:41,780 And also we'll go, well, actually, we want we're curious if it's not visited. 37 00:02:41,830 --> 00:02:50,080 So I'm going to say if not visited her, then we can go ahead and visit it. 38 00:02:50,350 --> 00:02:52,420 So we will. 39 00:02:52,690 --> 00:02:53,710 Let's see. 40 00:02:53,920 --> 00:02:55,260 We also need to process it. 41 00:02:55,270 --> 00:02:57,100 So we'll market is visited first. 42 00:02:57,820 --> 00:03:04,000 So Phil visited her equals one to replace the zero with the one to make it true. 43 00:03:04,690 --> 00:03:07,150 Then we'll just our processing is just printing it out. 44 00:03:07,150 --> 00:03:08,590 Remember, that's all we're doing. 45 00:03:08,770 --> 00:03:11,050 You can do whatever you want her processing it. 46 00:03:11,050 --> 00:03:14,590 But right now, just for simplicity's sake, we are just printing it out. 47 00:03:16,620 --> 00:03:24,240 So if it's not visited and we visited, Martha visited as true and we process it, and at this point 48 00:03:24,240 --> 00:03:28,920 we are ready to look through its neighbors no makeup for a loop where we loop over the actual chars 49 00:03:29,430 --> 00:03:33,900 and the string that is the value of the map. 50 00:03:34,140 --> 00:03:45,300 So do auto and in four node in the adjacency list, which is still in our graph. 51 00:03:46,230 --> 00:03:50,550 So the adjacency list care will give us that string of neighbors. 52 00:03:50,970 --> 00:03:58,050 And then what I'm interested in now is if it's not visited, remember, we're going to put this if check 53 00:03:58,050 --> 00:03:59,220 in here too. 54 00:03:59,310 --> 00:04:02,260 So we don't have those redundant flashbacks to the queue. 55 00:04:02,700 --> 00:04:15,030 So if I say if not visited in the node that we're currently on, then for that then we can push it back 56 00:04:15,030 --> 00:04:15,410 to the queue. 57 00:04:15,420 --> 00:04:16,770 So I'm just going to do only that one. 58 00:04:16,780 --> 00:04:17,280 I think so. 59 00:04:17,280 --> 00:04:20,760 I only need those brackets. 60 00:04:21,300 --> 00:04:28,030 So we would do VSK Q Dot push back in. 61 00:04:30,490 --> 00:04:35,180 Cool, so I honestly think that that is all we need, let's make sure. 62 00:04:35,350 --> 00:04:37,750 Also, I hope this is big enough for you guys. 63 00:04:38,320 --> 00:04:40,000 Zoom in just a little bit more. 64 00:04:42,100 --> 00:04:42,550 Yeah. 65 00:04:44,130 --> 00:04:44,700 So. 66 00:04:47,380 --> 00:04:48,990 Typekit, let's see, we have here. 67 00:04:49,320 --> 00:04:53,550 We pushed back the initial starting more attacks than we start our loop where we're going as long as 68 00:04:53,550 --> 00:04:54,430 it's not empty. 69 00:04:54,450 --> 00:04:56,500 We're getting the first thing from the queue. 70 00:04:56,550 --> 00:05:02,850 So the first thing would be see, in the case of our example, that we had the theoretical example, 71 00:05:03,480 --> 00:05:05,280 we get the first thing, pop it off. 72 00:05:05,490 --> 00:05:09,940 Then we're checking, Hey, is this is this thing visited if it's not visited? 73 00:05:09,960 --> 00:05:11,520 Let's go ahead and visit it. 74 00:05:11,520 --> 00:05:16,560 Market is visited and then process it, then for all of its neighbors. 75 00:05:17,630 --> 00:05:23,250 We are going to go through, and if one of the neighbors for each neighbor, the neighbors not visited, 76 00:05:23,250 --> 00:05:24,860 then we're going to push that back to the queue. 77 00:05:26,400 --> 00:05:32,310 And that is pretty much it, I think, to go down here, this is still left as depth first search. 78 00:05:32,310 --> 00:05:36,980 So I'm going to change this to BFS and this is just us passing this starting node. 79 00:05:39,430 --> 00:05:43,330 If you remember that and then all this stuff is already set up, I'm going to use the same file, which 80 00:05:43,330 --> 00:05:47,200 is actually from the lecture that we did. 81 00:05:47,200 --> 00:05:50,650 It is going to be the first graph that we went over that had more notes. 82 00:05:50,650 --> 00:05:54,700 Remember when we did the slide with the Q, that was a slightly smaller graph. 83 00:05:55,420 --> 00:06:00,460 So I'm using the the big graph that we walk through now and I can bring it up to check it once we run 84 00:06:00,460 --> 00:06:02,260 this so we can make sure that it's correct. 85 00:06:03,880 --> 00:06:08,710 So, yeah, I already have my edit configuration setup so you can go ahead and do that and then we're 86 00:06:08,710 --> 00:06:12,160 going to run this and see if we got a correct output. 87 00:06:14,410 --> 00:06:16,060 So let's take a look at this. 88 00:06:16,110 --> 00:06:21,790 This is a city that is not correct, so we must have done something wrong. 89 00:06:23,040 --> 00:06:26,910 So, Kurt, not me, that jumps out to me right away. 90 00:06:28,230 --> 00:06:32,820 We want to seek out care and process care because that's what we're doing right here. 91 00:06:32,850 --> 00:06:35,730 We don't want to be, you know, that's just the same starting vertex. 92 00:06:35,730 --> 00:06:37,360 That's why I printed out all CS. 93 00:06:37,380 --> 00:06:38,490 I'm pretty sure so. 94 00:06:39,630 --> 00:06:41,640 Let's change that small mistake. 95 00:06:44,490 --> 00:06:47,590 OK, see, ADF, FBG, JCI. 96 00:06:48,420 --> 00:06:53,650 Let's go ahead and bring up this, so and this is our slide. 97 00:06:54,510 --> 00:06:58,800 We have see a the. 98 00:07:00,980 --> 00:07:01,490 If. 99 00:07:03,560 --> 00:07:04,190 Be. 100 00:07:06,730 --> 00:07:08,610 And then G6. 101 00:07:10,250 --> 00:07:11,060 J. 102 00:07:13,010 --> 00:07:15,140 H e. 103 00:07:15,590 --> 00:07:15,960 I. 104 00:07:16,540 --> 00:07:17,790 So PR. The same order. 105 00:07:17,810 --> 00:07:19,370 And honestly, if you're using the same. 106 00:07:21,170 --> 00:07:26,090 Text file, it might print out in a slightly different order, but it will still be and still should 107 00:07:26,090 --> 00:07:26,690 be correct. 108 00:07:26,810 --> 00:07:29,610 So remember we can have different orders. 109 00:07:29,630 --> 00:07:35,270 The point is just to have the correct breath first search order where we're visiting all the neighbors 110 00:07:35,270 --> 00:07:38,420 first, so you can still trace it through if it's different. 111 00:07:38,930 --> 00:07:42,770 For example, maybe we didn't go to a first term. 112 00:07:42,770 --> 00:07:43,060 See? 113 00:07:43,140 --> 00:07:47,870 Maybe, you know, f- as a neighbor, maybe we went to F and then D and then a something like that. 114 00:07:48,140 --> 00:07:51,920 And that would change the order, but it still is a valid breath for a search traversal. 115 00:07:53,000 --> 00:07:59,180 So I just like modified my text, file my input file a little bit just to make it match what we were 116 00:07:59,180 --> 00:08:01,130 doing here in the graphs so we could compare it. 117 00:08:01,130 --> 00:08:01,790 Exactly. 118 00:08:02,900 --> 00:08:08,540 But yeah, it looks like our breath research is in fact working, and it's all good to go. 119 00:08:09,260 --> 00:08:10,580 So pretty simple. 120 00:08:11,390 --> 00:08:12,980 You know, not very different. 121 00:08:12,980 --> 00:08:16,700 We didn't change a whole lot from our death for a search, as you saw it's. 122 00:08:17,690 --> 00:08:22,400 You know, pretty similar to the iterative death research I think of IDF research we did was actually 123 00:08:22,400 --> 00:08:28,300 a recursive, whereas this is iterative and so you can do research recursively too. 124 00:08:28,310 --> 00:08:29,450 But I mean, I could go over that. 125 00:08:29,450 --> 00:08:31,880 It's easy if you want to look it up, it would be a quick change. 126 00:08:33,770 --> 00:08:40,190 So, yeah, with that, hopefully this is clear enough for you. 127 00:08:40,580 --> 00:08:43,590 Definitely good to try some different graphs. 128 00:08:43,610 --> 00:08:48,110 That's a good way to practice, you know, make some different graphs with the different characters 129 00:08:48,110 --> 00:08:48,500 and just. 130 00:08:49,420 --> 00:08:51,460 Tweak it and trace it and. 131 00:08:53,640 --> 00:08:59,400 Yeah, you know, really interesting algorithm, we will look at some more applications of this. 132 00:08:59,760 --> 00:09:07,170 It's kind of similar to if you look back to binary searches, it would be similar to like traversing 133 00:09:07,620 --> 00:09:08,670 level by level. 134 00:09:08,670 --> 00:09:14,100 A level order traversal of a binary search tree is kind of related to breath research. 135 00:09:14,100 --> 00:09:22,050 So we'll get into maybe a few applications and problems with breath research just so you can feel more 136 00:09:22,050 --> 00:09:22,620 comfortable. 137 00:09:22,830 --> 00:09:26,490 But hopefully this was enough to explain the general concept. 138 00:09:26,790 --> 00:09:27,030 All right. 139 00:09:27,030 --> 00:09:28,500 So with that, I'll see you in the next lecture.