Depth-First & Breadth-First Search Usage

[00:00:00]
>> Bianca Gandolfo: So the question is, for our recommendation, what do you think is better? So, the path we wanna take is, we want to find a person and then find a mutual interest. Like a mutual thing that I don't already like, you guys have a sense of what would be better?

[00:00:29]
>> Speaker 2: That first date.
>> Bianca Gandolfo: Why?
>> Speaker 2: Well, you're gonna go immediately to your food, which is gonna go back to another person, and then the third thing is gonna be into food, maybe. Actually, I take it back. I take it back.
>> Bianca Gandolfo: You take it back?
>> Speaker 2: Yeah.

[00:00:44]
>> Bianca Gandolfo: So you think breadth first search then?
>> Speaker 2: Uh-huh.
>> Bianca Gandolfo: Okay. What do other people think?
>> Speaker 3: Are you the starting note in this,
>> Bianca Gandolfo: What's that?
>> Speaker 3: Are you the starting note?
>> Bianca Gandolfo: I am the starting note in this.
>> Speaker 3: So we do browse first, and we'll see all the things that you like already first, right?

[00:01:06]
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: So would it make sense to go depth first to get away from the things that you're already connected to?
>> Bianca Gandolfo: Yeah. That could be a strategy like, the furthest thing away from me would definitely be something that, let's see if I have, where is that graph?

[00:01:27]
So,
>> Bianca Gandolfo: Here's a different version of the graph. So if we go depth first, right? We can make it there faster. Whereas, breadth first would do this first and then the people, and then it wouldn't be this one, right? So I think my recommendation would be, if you're just trying to find one thing, right?

[00:01:51]
Like we just need one recommendation. Do that first, but if you wanna have multiple recommendations it might be nice to do breadth first because then you would just have that list at the level. You know what I mean? All at the same time.
>> Speaker 3: It's just, I feel that it should be two different trees that you're connecting.

[00:02:11]
It shouldn't be in the same, like that. It shouldn't look like this.
>> Bianca Gandolfo: Why?
>> Speaker 3: Because, maybe you could have your, I guess it can look like this but,
>> Speaker 3: Because I don't know, it's organized better like if you have people's recommendations and then. Then how are the people connected to each other, and then the food that heir people are connected to, that's one way to do it.

[00:02:44]
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Or, I guess, here you have your food, your first breakfast, your number one breakfast repetition.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: And then you have your people, and then their recommendation.
>> Bianca Gandolfo: Yeah, this is just a traversal, actually the graph looks like this.
>> Speaker 3: Right. That's, yeah.
>> Bianca Gandolfo: But when you traverse it, it kind of starts to look at a tree, right?

[00:03:03]
>> Speaker 3: Right.
>> Bianca Gandolfo: Cuz you only visit each day once.
>> Speaker 3: Okay, I see what you're saying.
>> Bianca Gandolfo: Yeah, so they're actually the same thing. This is just like a traversal.
>> Speaker 3: I see what you're saying.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: It's like a tree of the traversal.
>> Speaker 3: Right.
>> Bianca Gandolfo: But the graph still is the same as it was.

[00:03:21]
>> Speaker 3: But this traversal, it shouldn't the traversal be different for the DFS versus BFS, or are you asking?
>> Bianca Gandolfo: The traversal, the DFS goes like this.
>> Speaker 3: Yup.
>> Bianca Gandolfo: And then the BFS goes like this.
>> Speaker 3: I see what you're saying.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: So the DFS looks better because, at least you'll know if there's recommendations right away.

[00:03:47]
>> Bianca Gandolfo: Yup, yeah, I mean you do a lot less work.
>> Speaker 3: To get a recommendation.
>> Bianca Gandolfo: Yeah, right, so like this one, we would have to do one, two, three, four, five, and if there was even more, right, keep going until we got here. And you can imagine this could be huge.

[00:04:04]
Yeah, I like those few things, but there are a lot of things I like for breakfast, and there's a lot of things that my friends like for breakfast. So, yeah.
>> Speaker 4: Okay, there is no issue with your code, there's just an issue with my code.
>> Bianca Gandolfo: Okay [LAUGH] all right, great.

[00:04:25]
All right, so just like thinking more about breadth first search and depth first search, and just these traversals in general, what they're used for? What kind of questions come up, that these are suited for. So, we have logging and validating which we've been doing a lot of, right?

[00:04:44]
We're logging all over the place, but validating is useful to which you get to like binary search trees which is, there's like certain rules that has to follow and traversing that and validating it is important. So, there's similarly like copying is another thing that you might wanna do, counting edges or vertices.

[00:05:07]
There's another one or you even leaves that we were doing earlier. Identifying if a component is connected in a graph like I mentioned, you can add a note to a graph, but it doesn't necessarily have to have an edge to another node. And so you can test if things are connected and sort of like a social media world this might look like is someone in your LinkedIn network, right.

[00:05:32]
Or, like are there clicks in,
>> Bianca Gandolfo: I don't know, Twitter, what else? And then finding paths or cycles are pretty common interview question. So a path is, can you get from point A to point B, right? And then cycles is, can you start at point A and come back to point A through this graph?

[00:06:03]
So detecting cycles, finding paths, shortest paths, things like that. So shortest path's gonna be breadth first search for sure. There's a few different algorithms to get you there, but they're all breadth first search base algorithms with optimizations.