Transcript from the "Pseudocoding DFS Part 1" Lesson

[00:00:00]

>> Bianca Gandolfo: So we're gonna pseudocode this, and then we are gonna talk about breadth-first search. And we're gonna pseudocode that, and then that might be the end of our day, and you guys can go home, and code like crazy on your Friday night. Cuz I think that's what you were planning to do, right?

[00:00:15]

>> Speaker 2: [INAUDIBLE]

>> Bianca Gandolfo: And then we'll do the solutions tomorrow morning. That sound like plan? Sounds solid? Okay, here we go. So we wanna do a depth-first search on our graph, knowing that our graph is an adjacency matrix.

>> Bianca Gandolfo: Cool? So, what order do you think that we might go?

[00:00:49]

>> Bianca Gandolfo: If we were to explore this graph in a depth-first search.

>> Speaker 2: Can we just go all the way across the first array? Should be down the left column, right? So we got 1, 2, 3, 4, 5.

>> Bianca Gandolfo: So you can only traverse if there's a connection.

>> Speaker 3: I was just gonna say, do you have to pay attention to that?

[00:01:08] Okay.

>> Bianca Gandolfo: Yeah.

>> Bianca Gandolfo: So without looking at the adjacency list, just give me an example path.

>> Speaker 3: 1, 2, 4, 5, 6.

>> Bianca Gandolfo: Mm-hm, yeah, so that would be depth-first, so we could start at one. We visit 1, we visit 2, we visit 4, we visit 5, we visit 6.

[00:01:40] 6, we check if there's any adjacents, and it's explored. Once there's nothing, it's explored. We go back. 5, we check, it's been explored. 4, explored because these are direct you can't go backwards. 2, explored. 1?

>> Speaker 3: It's not explored.

>> Bianca Gandolfo: Not explored, good. 3?

>> Speaker 3: Not explored.

>> Bianca Gandolfo: Visited.

[00:02:09] 4?

>> Speaker 2: [INAUDIBLE] [CROSSTALK]

>> Bianca Gandolfo: Is explored, so we come back. 3 is now?

>> Speaker 3: Explored.

>> Bianca Gandolfo: Explored. And now we're done.

>> Speaker 3: So you can only go back on cycles?

>> Bianca Gandolfo: Well this is just happens to be a directed graph. So if it was undirected then you could go either direction.

[00:02:41]

>> Bianca Gandolfo: But it's been proven that if it's connected and you do depth-first search, you will visit all the nodes at least once. And probably twice if it's undirected. Because you'd go both ways. Or at most, twice. Make sense? Okay.

>> Bianca Gandolfo: All right, so first things first. We have to start somewhere.

[00:03:16] So we'll start with 1.

>> Bianca Gandolfo: Then what do we do? Now we're looking at the adjacency list, right? Our implementation is based on the adjacency list, but being mindful of how we should be traversing in the actual graph. That make sense? Okay, so we start with 1.

>> Speaker 2: [INAUDIBLE]

[00:03:46]

>> Bianca Gandolfo: Hm?

>> Speaker 2: Go to left to 2, 2.

>> Bianca Gandolfo: Yeah, so go left. So we can say, so we'll start with 1, and when we say start, we can just say let's visit 1.

>> Bianca Gandolfo: And then we'll visit 2, right?

>> Bianca Gandolfo: visit 4.

>> Bianca Gandolfo: visit 5.

>> Bianca Gandolfo: visit 6.

[00:04:33] Right? That's what we're doing. This is gonna be our recursion, right? Does that make sense? Okay, so we're visiting down, down, down. Once we get to the bottom, so we say like once there are no more unexplored.

>> Speaker 3: Nodes?

>> Bianca Gandolfo: Nodes. return.

>> Speaker 3: In that tab.

>> Bianca Gandolfo: Mm-hm, yep.

[00:05:26]

>> Bianca Gandolfo: So we're getting there. So once we got to the bottom where we turned up. Then we're returning up from 5. Where are we now?

>> Bianca Gandolfo: So, these are recursive calls, right?

>> Speaker 2: Mm-hm.

>> Bianca Gandolfo: Does that make sense to you? So, we return up from 6, we return up from 5.

[00:05:48] Every time, we're checking for what?

>> Speaker 3: Another connection?

>> Bianca Gandolfo: Mm-hm. So, we have explored, we have visited, and we have undiscovered, right? So, the only one that we have undiscovered right now is 3. And we can return once there are no more unexplored.

>> Bianca Gandolfo: Or is it unvisited?

[00:06:22] Now I'm confusing myself. We'll find out. Either unexplored or unvisited. Mm. Yeah, either way. We haven't been there yet. So once you've been there, all the places. So 6, there's no places to go, so return. 5, we check 6. 6 has been explored for sure, right? Cuz there's nothing left.

[00:06:51] So explored means we visited all of its adjacent nodes, okay? And then we're at 4, and we can check 4. What's adjacent? 5 has been explored, right? Because of 6. And 4 is gonna go back to 2. 2, it's gonna look at four, but it's been explored, so it's not really gonna go in there.

[00:07:22] It's not gonna recurse in. And then 1. Then we see, okay, 2 has been explored. And then we go, we look at 3, which is actually undiscovered, we visited it. And then we go to 3. While we're visiting it, we wanna see [COUGH] if we can go anywhere from there.

[00:07:44] Then we can go to 4. 4 is explored so we come back. Now 3 is explored cuz there's nowhere else for it to go. And then we go back to 1.

>> Speaker 3: So you end up going to 4 three times?

>> Bianca Gandolfo: Yeah, we're not actually really inspecting it three times.

[00:08:07] You're just popping back into that layer one of the times. So you should only explore it, the number of. Well, you only explore it once, but you visit it twice.

>> Bianca Gandolfo: That make sense? Cuz exploring is when you actually go there, and then you keep traversing into its adjacent, into all of the edges.

[00:08:33]

>> Speaker 3: Okay.

>> Bianca Gandolfo: Yeah, so that's exploring. So you visit it, and then once it has been explored, then that means you've seen it all. You've seen all of its-

>> Speaker 3: So, in order to explore 3, you have to see that it's connected to 4?

>> Bianca Gandolfo: For 3 to be explored, that means you already visited 4 and left.

[00:09:04]

>> Speaker 3: Okay.

>> Bianca Gandolfo: So there's nowhere else for it to go, and so now it's explored and you just mark it black.

>> Speaker 3: Right, yeah.

>> Bianca Gandolfo: Yeah.

>> Speaker 3: Yeah, yep.

>> Bianca Gandolfo: So you're done with it. There's nothing else for you to do. You already did your business, whatever it is that you're doing.