Transcript from the "Breadth-First Search" Lesson

[00:00:00]

>> Bianca Gandolfo: Breadth-first search is the kind and humble sibling of depth-first search. You might guess that depth-first search is called depth-first search because we first search deep into the data structure before going anywhere else. And breadth-first search has nothing to do with baking or bread, despite its name. We're talking about breadth in terms of wideness, right?

[00:00:28] And so you can imagine as we traverse our graph or a tree, that we're first going out and then down, right? And it looks a bit different for a tree versus a graph. And I'm gonna show you a tree first, cuz I think it's easier. So here's our tree for our breadth-first search.

[00:00:48] You can see that our path is going to start at some top node, right, this is probably our root node. And then we're gonna go from B, C, and D, so breadth, wide, and then E, F, G, H, and I. And in the order, the specific order, right, this one's going from left to right, you get to this side, right?

[00:01:11]

>> off screen: It looks like it's reading a book.

>> Bianca Gandolfo: Yeah, it's kinda like reading a book, and so that's breadth-first search.

>> Bianca Gandolfo: It's a different kind of search. And again, these are the foundational pieces of bigger and more complex algorithms that do cool things. And I'll talk about at the end what those things are.

[00:01:37] So here's a diagram of breadth-first search with the grey and the black and the white concepts, so white is undiscovered. We visit, we visit, we explore, we explore, explore. Cool, so level by level. When this is a graph, we measure the depth of the graph by how far away it is from a particular node.

[00:02:08] So let me look at a picture. So if we were starting a breadth-first search from 4, we would explore. Since this isn't a tree, this is not a tree, it doesn't necessarily have a root node or anything like that, we can start anywhere. So first we would explore 2, 3, and 5, before then exploring 6.

[00:02:34] And then actually we couldn't explore 1, because the directions won't allow us. But hypothetically if this was an undirected graph, we would then visit 1. And then the specifics right in between, do we do 5 first, do we do 2 first or whatever, is up to your specific implementation.

[00:02:51] And it mirrors pretty closely kind of how we did in order, pre-order, post-order. So just like you can tweak things a little bit, cool? And so here's a procedure for breadth-first search. So the core of breadth-first search is a queue, which is the opposite of what the core data structure for a depth-first search is.

[00:03:21] Can someone guess? So we actually don't explicitly use a data structure in our depth-first search, but we're implicitly using a data structure underneath. Can you guess which one that is?

>> Bianca Gandolfo: Here's a hint, it's recursion. And whenever we do recursion, when we start pasting things over and running through the code, what is that?

[00:03:44]

>> off screen: Stack.

>> Bianca Gandolfo: Stack, yeah. So the core of depth-first is a stack. We can do that either explicitly, by creating a stack, or we can do it by having recursive calls and the stack is taken care of for us behind, okay. So depth-first search we have a queue.

[00:04:05] We don't have anything happening behind the scenes that's giving us a queue necessarily in this case. So we'll first create our queue. And we're gonna queue up things in order by layer, right, not by depth. So we have this while loop. And we say while queue is not empty, perform the following steps.

[00:04:29] You're gonna dequeue, mark it as discovered. Enqueue all unvisited neighbors. And then mark it as explored once it's unqueued. So that is sort of the core of the procedure. And then we're going to pseudocode it now that we've peeked, okay