Breadth-First Search

[00:00:00]
>> So let's talk about the types of traversals you do in a graph, which there's two of them, breadth-first and depth-first. We already covered this in the previous algorithms course, including this intro. I just wanted to do it one more time, so nobody is lost. We're not gonna go super in-depth on these things.

[00:00:15]
So, we'll erase the representation. We don't care how we're gonna be representing the graphs, because we're gonna be doing algorithms across them, okay? Though representation does make a big difference on potentially the runtime speed of an algorithm, because if you have to set up an adjacency matrix, you have to put in the squared amount of items.

[00:00:33]
You can't get away from that, that's just just how it works, it's just life. That is what it is. All right, so, let's do a quick breath-first search. All right, I'm gonna go like this, and we're just gonna make a fun graph. All right, and then, I should write some letters in there, right, C, D, E, F, G H.

[00:01:01]
It really bothers me that I went lowest, lowest, and then, lowest, and then went inverted, at the very end. I don't know why I did that, just really upsetting. All right, so we're gonna do a breadth-first search right here. That means, we pick a node, we'll just say, A, and we're gonna go and we're gonna take a queue to kind of help us walk this graph.

[00:01:21]
All right, so breadth-first search is really, really simple. It's starting node, pick that, add all the edges to that, mark this thing as it visited, and then, pop the next item off the queue until there's nothing left in the queue. And you just do that over and over again.

[00:01:37]
So we have A. A is in our queue queue to begin with. What do we do with A? We get A out of there and we mark A as visited, but instead, we put in B and C. All right, awesome. So now, we just pop the next item out of our queue.

[00:01:52]
So we have visited A. Now, we're gonna visit B. B will be marked as visited, we can add an A, A has already been visited, we don't need to do that. We need to add in D, fantastico. So we go C, D, all right? Now, we pop it out again.

[00:02:08]
We get C and we visit C. And then, we try to add D, D is already in there. You could technically, you could technically make an algorithm in which you actually have both D's. And then, when you take out the second D, you check to see if you've already visited this one.

[00:02:21]
And if you've already visited it, then just keep on going forward, you don't have to retry to add the edges, all that. So, either or, and so, now, we pop off the next D, and we add in E, F, G, and H. E, F, G, and H, awesome.

[00:02:40]
And so, now, we pop off the next D. We've already seen that D. Move it on, go with the E, E comes down. We have now visited E, E has been visited, E has no neighbors to add, D has already been visited, so we move on, we pop off F, exact same thing.

[00:02:54]
Pop off F, visit F, F can only add D, D has already been added. We've already seen it, so we pop off G, G goes on here, mark G has visited. D has already been added, we don't add D. Then we pop off H, H goes here, tries to add D, D has already been visited, and now we go try to add I, I has not been visited.

[00:03:12]
I goes into the Q and now we write I, and we pop off I, and we do all the marking, and we do all the great stuff. That is a breath-first search, we use a queue to manage how we visit things. Now, there's a very special property with breadth-first search.

[00:03:24]
Notice that this is 0, that this is 1, that this, all the way not there. This is 2, and this is 3, meaning that we are at A, that is where we start our breath-first search. We are able to find, either of these people in 1 hop, we are able to find D in 2 hops, I did that wrong.

[00:03:46]
D goes like that, D is 2, this is 3, this is 4, then E, F, G, and H are 3 hops away, and I is 4 hops away. Breath-first search goes out in concentric rings in some sort of sense. It finds further and further away nodes, which is pretty cool, because you know the really neat application of breadth-first search is, if you have a weightless undirected graph, let's just go like this.

[00:04:17]
We're almost there, can you feel it? Are you excited? We have a start, we have an end, and we have walls. A breath-first search will literally find the shortest path from S to E by the very nature of how it works because it walks in these little further distance rings.

[00:04:38]
Meaning that, if we can only go left, right, up here, we'll do it in this order too. We go up, we'll go top, we'll do CSS order, right? Top, right, bottom, left, all right, fantastic. CSS order that has never been stated once in a class about graphs. Okay, I think I'm the first person ever to say this phrase.

[00:04:57]
All right, that means this would be distance 0. This would be distance 1. This will be distance 2. This will be distance 3, there we go. This will be distance 4, this will be distance 5. This will be distance 6, 7, 8, 9, 10. And so, you can see this thing slowly going out, because we'd walked it.

[00:05:30]
So if I were to actually do this in this order, I'd go 1, then I'd go 2, then I'd go 3, right, we've kind of go in this ordering where we actually do it one at a time. And you can see the path this thing takes because it just do them all at the same time.

[00:05:47]
And that's how we'd all add them in. And so, that's how breadth-first search works, it's pretty neat, that it actually creates this nice little path. That is the shortest path from start to end following our rules. So if we were to add diagonals, obviously at that point, we would have been able to go 1, 2, we'd have been able to just kind of go right there.

[00:06:04]
And it would have been able to find all those within those rings. Alright, good times, depth-first search. Good to know, by the way, this is kind of like the basis of Dijkstra's. I went over Dijkstra's last time, so I'm not gonna be doing it this time, but Dijkstra's shortest path, fantastic.

[00:06:18]
Then there's A star, even more fantastic. Then there's Jump Point Search, which is even more fantastic. Then there's Jump Point Search Plus, which is even more fantastic. I think they use one of these two in StarCraft for moving things across these already known fields and all that. Because if you really think about it, if you have a big graph and you have these little structures here, really, you could take the entirety of the movement here and put it into points.

[00:06:41]
You don't have to walk every last little teeny tiny point in the graph, you just walk the thing, right? And these little fun, these fun algorithmic kind of challenges you get to do in game programming. I'm not a game programmer, I'm not talented enough to be a game programmer, is very hard job, bless their hearts, love Baldur's Gate.

[00:07:00]
All right, so now that we did that, let's erase the stuff, okay? Erase the things. I'd like to keep this graph, but I have to rewrite it. I've kind of made it really hard to see, okay, just forget about it, you're dead.