OK, so let's go ahead and move on to the actual algorithms now for traversing graphs.
So this first algorithm is going to be depth first search, which I have abbreviated here DFS.
So let's get right into it.
So we've talked about graphs a little bit, but what if we want to traverse a given graph and then make
sure that we visit every single node or vertex while we traverse it in complete and completion, like
from some starting node all the way through it and coming back to where we started, but making sure
that we stopped at each one of the nodes.
There are multiple ways you can do that.
Two of the most popular ways are depth first search and breath, first search.
And in this lecture, we're going to be talking about depth, first search.
So as the name implies, you search deep first.
So that would be like just taking a path, continuing on some path until you get to the end.
Rather than like visiting everything that stems out from a vertex would be which would be breath for
a search, which we'll talk about later.
So you try and go deep first and then you basically come back when you can't explore anymore and then
you explore another path going deep again.
So let's look more into that.
We're going to go ahead and traverse this, I have put some letters here is labels for the vertices.
So we will start traversing it in depth first search fashion until we have visited all the nodes and
are back where we started.
So you can pick any starting point.
I am going to pick see right here.
You see that I'm also going to be labeling the order in which I am exploring and visiting these vertices.
But you can pick any starting point and then from any given node link, for example, here you see that
see has the potential to go to a D or F.
You could really choose any one of those.
Any one of those is going to be a valid move on a depth first search algorithm path.
So I'm just going to go ahead and choose a.
And once I have chosen a you see that I have also labeled it as the second note that we have visited.
So from a I can go to B, and that is because I could also go to see from A.
But we've already visited.
See, so that's why I'm going to go to be so from B.
We have a lot of choices since we've already visited A.
We won't consider that, but we have D, E, H and J, so we'll go over to H.
You notice that H has no other neighbors besides the one that it came from, so no other adjacent vertices.
And so we're going to have to go back to B and then so after we go back to B, we can explore E is the
same situation as F.
Basically, there is no other adjacent businesses besides the one we came from.
So we go back to B again and then we will go out to D.
Vardy visited to see, so we had to f already visited D, so we had to g r f, so we had to I I has
no other businesses to visit, so we come back to G.
Everything is visited from G already, so we go to f same case for f f.
Everything is visited.
Go back to D because that's where we came from and then everything's visited there.
We got to D from B, so we go back to B and everything is visited there.
But except for this, J, so all of these are visible, except for this J.
So we will go out to this J.
The Jazz, the same cases, the H in the E and I, there's no other adjacent verses, so we have to
go back to B.
We originally came to be from A.
So we'll go back to A..
And then we originally came to a from C, so we'll go back to C.
And now we have visited everything and gone back to where we started out.
So that was a lot.
How do we even do all of this in code, you're probably wondering.
And one of the main things is how do we know where to get back from, where we came from?
So that is actually the reason why I started out first by going over the stack in the queue data structure
because those are both going to be necessary for this section.
So the stack in particular is going to be used with depth first search.
And you can think of this as the stack that we just went over in that previous subsection about Stacks
and Qs, where we had an actual steel container, which was the stack and we were pushing things to
it and probably things from it.
Or you can think of it if you're going to implement depth first search as a recursive algorithm, you
can think of it as the call stack.
The recursive call stack like functions and stack frames from recursive calls.
That stack functions in the same way for us for depth for search, so we can do both a recursive version
and an iterative version where we the iterative version, we would implement our own stack in the recursive
version and we could use a call stack.
So you can think about it either way, I'm going to go ahead and walk through this depth first search
traversal of this graph again, just like we did, but I'm going to use a stack over here and you can
think of it as the recursive stack or the iterative kind of like we would have our own stack that we're
pushing to.
The way that I'm going to be talking about.
It is slightly more aligned with the iterative algorithm, but it can work either way.
So let's get started.
I'm going to start out at sea again and I'll be labeling them again.
So from see, I went to a room, and since I went to a from see, I am going to push that to the stack.
So I push sea to the stack there from a I went to B since I came from a push eight in the stack.
From B, we have all these choices, J.
C and D..
I go to H.
So I push B to the stack because I came from B h we can't explore anymore, like we said.
So we have to go back to B.
And at this point, the reason I know how to go back to B is because B is at the top of the stack over
here.
So when I'm when I can't explore anything else, I'm basically going to be like, OK, what's at the
top of the stack?
Oh, be great.
I'm going to pop that off now I'm at B, so that gets popped off the stack.
So now we had to E!
And same thing since we came from B to E, we're going to have to push B back to the stack.
So I push back to the stack.
Nothing to explore from here.
So we come back to b same thing.
Pop it off and then we're going to head over to D just like we did before.
We need to push B back to the stack because we came from B.
Already saw see, so we're going to head to F..
So let's go ahead and head to F. And then we're going to push to the stack since we came from there
already saw D and C, so we're going to head over to G.
And after we do that, we're going to push F to the stack.
Same thing.
We'll head to AI and one plus g to the stack and then I we can't explore anymore.
So we have to come back to G.
And the way that we're doing that is looking at the top of the stack, which is Gee.
And so we pop that off now we're at G.
Where do we come from to get to G F and we're looking at that because we can't go, everything's been
explored already, so.
You know where we come from, effortless pop that off now, we're f same situation where we explored
everything we came from D, because that's at the top of the stack.
So pop that off.
Now we're at the.
Go back to be because that's how we got to D and that's at the top of the stack, that's how we know
why.
And then now that we're it be, we can explore.
Jay, so let's go out to Jay because that's unexplored since we went out to Jay from B, where push
B back to the stack can explore anything from Jay, so we have to head back.
So what do we have to act to be?
He's been pushed and popped a lot, but we're going to have to pop it again from the stack.
And now everything from B has been explored as well, so now we're going to have to see where to head
back to from B, which is a that's at the top of the stack.
So head back to A and then everything's being explored from A..
So where do we have to?
What's at the top?
C is the only item left.
It's at the top.
We have to see and we are done with our depth.
First traversal depth.
First search to Russell now.
So like I said, you can think of those as kind of like recursive calls, whereas like each stack frame
would have been for the particular node.
Otherwise, if you're doing the iterative algorithm, it would be kind of like once you are going out
to.
Basically, explore another Vertex, you're going to have to push the one that you came from, so let's
go ahead and continue.
So another important thing to note is, you know, and I was saying, OK, we've already seen this or
we've already seen that, and I had marked yellow ring for when we visited something.
We need a way to keep track of that.
So you might have been thinking about how to do that already, but a pretty good way is to have some
container for that.
And I like to just fill it all with zeros and then basically you have indices that align with the specific
vertex.
And if you visit one, you just change the zero at that specific vertex index to a one.
So that's a way to keep track of which ones are visited and which ones are not.
If it's a zero is unexplored.
If it has a one there, it's already been explored.
It's already been visited.
So definitely want to think back to our two ways of implementing graphs, so we have the adjacency list
and the adjacency matrix in addition to it, like I mentioned, there's two ways to implement the dips
versus traversal, which is recursive and iterative.
So we have two types of implementations for the graph and two ways to implement the depth of research
traversal.
There could be multiple ways like thinking about it, you know, kind of like many ways, depending
on how you write your code, but.
I'm just talking about the two types of depth First Search recursive the narrative.
So let's look at some pseudocode here.
We have the recursive on the left and on the right.
I'll go ahead and start out with the recursive one.
So you can just imagine this is like maybe a void function.
And what's going to happen is this we this past, there's an argument.
Up at the top is the first vertex, the initial start vertex.
So we started C here.
Remember?
So that's what I'm talking about right now.
So all of this pseudocode is basically indented, and so all of this right here is in the scope of this
f block.
Same here.
All of this right here, this indented in is in the scope of the four and then this recursive calls
and the scope of the if so.
Not the strain of C++ and not straight up like Python or anything, it's just pseudo code, so just
wanted to point that out.
So if the Vertex is not visited, so all this only happens at the vertex is not vested in.
You're going to process the vertex, and this can basically be anything this is just the work you want
to do once you're on that vertex.
So we're just traversing the graph, but these nodes that we're traversing to, they can have any kind
of information there and you might need to like do certain things like call some functions and change
that information.
So whatever you need to do, that's going to happen right here.
And when we implement the code in the next video, I'm just going to print the vertex out.
So like, let's say it was like Vertex C, I would just print out, see, just to it, that's just for
the purpose of explaining the algorithm.
So we're we're not going to like do any fancy stuff because we want to focus on the algorithm.
But you could put anything here.
So just imagine an x thing you want to do goes here.
After that, you mark v is visited, so think back to this container here.
So.
You know, if we were at sea, we would mark sea one for sea.
Then you start a loop after that and you're going to go for every one of the neighbors of the current
Vertex V, so you're going to live through all of those.
So if you think about it, we have these two implementations here at the adjacency matrix in the Jason
C list.
And so since we're having to loop through all of the neighbors, it kind of changes the way we were
thinking about that before, you know, it was nice that we could just subscript this subscript index,
this matrix and have constant time to search for some given Vertex.
But the thing is that we actually have to go through all the neighbors of a specific vertex anyways.
So just want you to keep that in mind when you're thinking about like the efficiency of this or if you
remember back, one of the other things we talked about was that the adjacency list is slightly more
space efficient than the Matrix as well.
So something else to consider as well.
So either way, you want to imagine it.
Let's say it's an adjacency list when you'd have to come down and go through that list after we index
the original array or hash table or whatever you're using.
We would have to look at the neighbor list there and go through all of them.
So for each neighbor, if that neighbor is not visited, we're actually going to start this whole process
over again with a recursive call and pass that neighbor.
And that's basically synonymous with saying like, now let's explore from that vertex.
So we explored from one Vertex was like, you know.
Let's just say, hey, all the neighbors are there.
But since we're doing death for service, it's just like, OK, let's recall this function immediately
and just go deep.
You know, let's do a recursive call and head to that first vortex that was the first of the neighbors
or something like that.
And I said it didn't matter which one you go to first, but I'm just saying that now, you know, if
you're looping from like the beginning of this, you know, you of course, would like head to the first
one and then the next one.
Like, if you were on this in the foil loop and this was the first and you were just obviously call
this recursively with that first vertex neighboring vertex and start this whole process again.
So that is the recursive implementation.
And then the iterative implementation is very similar, except, of course, the stack frames in this
hour or if the stack in this is the stack frames itself.
So, you know, it's going in the order of these recursive calls.
So basically, when it gets down to the end, when it doesn't have any neighbors and it's not going
to hit this visited thing, this void function would just return and you'd be going back up the stack
and those stack frames would be popping off.
So the recursive process would work similar to us pushing and popping from an actual stack that we implement
over here.
So for the iterative one, though, we will have to push to an actual stacks, we have to create a stack.
This just assumes that we have one in the pseudocode and this is not going to be like necessarily perfect
C++ code.
Like I already said, it's just pseudocode, so just bear with me here.
We'll actually do the implementation in the next video.
So you push the first vertex to the stack, then you say, Wow, the stack is not empty because this
is like the key that we're done with it.
If the stack is empty, we have explored everything.
So whilst it's not empty, pop the thing off the top of the stack and store it in this car, if that
current is not visited, then market and then processes.
So marketing is like Mark is visited, markers visited.
It's like, I remember back to this, we would market in this container that we have.
Then processing will just be printing out for us then.
But you can do whatever you want here, of course.
Like I said, then you go through all the neighbors again, just like in the recursive implementation.
And the same exact thing if it's not visited.
Rather than doing the recursive call, which would make a new stack frame, we are just going to push
the neighbors to the stack.
So the one thing that's slightly different is that this for a loop will just go and just push all the
neighbors to the stack before we go back up to the top here.
And that's like the one thing that's different.
So all these neighbors will be already pushed to the stack and then we will go to the top of the while
loop and we'll just pop like the first neighbor off and then keep going.
So that's like the one thing that's slightly different than the recursive implementation, but they
really work the same.
So in the next video, we will actually be starting out with the recursive implementation and I will.
Most likely be introducing a not new date structure, but something we've talked about before and be
doing it in an adjacency list style, that's what I'll be using for the representation of the graph.
So with that, I will see you in the next lecture.