OK, so let's go ahead and implement the recursive depth first search within adjacency list, that's
what we're going to do in this tutorial.
You see, I kind of have some multiple windows open here.
This one right here will say click that and started, we're actually going to go over kind of once we
write this code out, we're going to step through it and see kind of what's going on with our with our
recursive algorithm just really hammered in there.
So you totally understand that the research that is the goal.
So I've just made a new project here.
It's just only going to have one actual C++ file, which will just be like a main file.
I'm going to put everything in here because the purpose is just to, like, make something pretty bare
bones, take some input from a file, build a graph and do this research on it and print it out.
So that is the goal.
We are going to be introducing something.
I've kind of already introduced it already and you might have checked it out or even used it.
But that is the unordered map.
We haven't really used it yet.
You might have used it, but we haven't used it in the course.
And so I'm going to use that today.
I would just use the map like a normal map, but.
An ordered map.
But if you recall, I think I said at one point that the unordered math is actually implemented at a
hash as a hash table type of table, and then the map is technically a like self-balancing tree.
I think it's a red black tree.
But for that reason, when we're thinking about like time complexity and the implementation details
of the adjacency list and stuff like that, I just want to use an ordered map just because I was thinking
some people, you know, might be like, Oh, hey, you know, you said Map was like a tree, and I
looked it up.
And like you said, all this stuff about time, complexity being this.
And so that's why I'm using an old map.
But you could use whatever you want.
Yeah.
So totally, totally up to you.
You can even use an array, kind of like I described in the beginning with the adjacency list, you
know, an array of links, lists or something like that.
But we'll get into the way I might do it in just a moment.
So I'm also going to include string and I'm going to include file stream, and I'm including the string
because what I am actually going to do is have it be a star like this.
So I'm assuming someone gave me an input file.
That's why I'm assuming that the this first letter right here will be a given vertex.
And then they there will be kind of like these characters, which are the adjacent vertices just smashed
together.
So I'm kind of going to use like get line, read into a string and then like, do some stuff by splitting
it up like that.
So that seems like the easiest way for me.
But however you want to do this, the point is just to go over a depth first search.
So if you want to do it a different way, more power to you?
Absolutely.
So do you using namespace to me, then I'm going to declare some kind of global data structures for
my visited container and my adjacency list, which will both be on ordered match.
So I will do unordered map.
And one of them's going to be charged for the specific vertex and then string will be the value.
For the key.
So that's kind of how this works, when you have a map or in an ordered map, you kind of write it like
you would a vector, like you write this and then you have, oh, don't want to do that?
You put these alligator mouth and then this first item is what the key is.
So this is kind of like the key that you'd be hashing on if you think back to the hash table things
we had, we went over.
And then this would be like the data type of the value that was stored.
So data type of the key data by type of the value stored by hashing into that key that that specific
index.
So this is going to be our Jason C list.
It is going to be basically what's storing this.
You know, this is the key in these.
This is the value which will be like a string.
So just to explain that.
Let me make another on map and this is just going to be for our visited.
So since I'm using characters like CAIB, EDF, I can see to the right, I am going to do something
that is char and then int like this.
So we're going to put a one or a zero there, remember?
So that's why I'm going to have the and I'll just call that visited.
OK.
And then the next thing that I'm going to do is just prototype my actual function for a depth first
search.
I'll call that DFS, and then we will be passing our char vertex to it.
So let's go ahead and just get right to implementing that.
So I'm going to do Boy DFS because I'm doing this first one here and then
what are we gonna start out with?
So is, if not visited the.
So if the vertex is being passed, it's not in the visited container that map, then I'm going to say,
see out, is this how we're processing it?
See V and then I'm going to put a little space because I'm going to print them all out in a line.
And then we're going to market is visited, so I'll say this, and then we equals one now.
So I'm assuming they are all zeros at this point.
You know, when I'm calling the function for the first time, it will be filled with zeros and then
now we can do our for a loop.
And so I'm just going to iterate over the actual items.
So I'm going to do one of these or I do cha and I call in and then my adjacency list.
And what we're going to do is use that key to get the neighbors because the adjacency lists remember
is like we're going to key in to a specific vertex and that's going to give us like a string which can
be indexed just like an array of our neighbors.
So we're kind of doing it, you know, instead of an array of link lists, we're doing a, you know,
a map where the values are like strings, which can be thought of as being able to index like an array.
So just slightly different than I explained in the lecture about the graph implementations, but we're
doing the same thing.
So I'm going to say, if not visited and then I, which is going to be, you know, each eye is one
of the neighbors.
So if the neighbor is not visited, then we are going to call the function recursively and this will
not be what it would be.
So we're going to pass the neighborhood to it.
OK, so that should be actually all for our depth first search function, pretty similar to what the
pseudocode that we showed in the last lecture.
So let's go ahead and make a main function and read into that file.
So I'm going to do it mean an ARG C
and char b.
So standard stuff here.
I want to make sure that we are, you know, passing an input file properly.
I put a little error message like we always do.
You say input file.
OK.
And then, of course, if this you know the case, then we'll exit with the negative one protection
code.
So let's make a stream and you can call in-stream, and then we will open the stream with the past hour
one, which is the file.
So all stuff that you guys have done before, and I'm going to do this.
So I'm going to live through and then I'm going to get a line and that'll have our whole line right
here.
And then I'm going to break this off and separate out the neighbors.
So I'm going to do get line and then I'm going to have the stream in here and then it's going to read
into my string s and then what I'm doing here is I'm going to index the adjacency list and I'm going
to basically create a new key and a value based on me chopping up like the first part of this line here
and then the second part.
So this will be key and then this will be value like I mentioned before.
And the way that we do that is just like the way we indexed it.
So I'm going to say adjacency list and then I'm going to have, you know, the string and index zero
of the string, which will be that first character on that line.
And then I'm going to say Equals s dot substring, so I'm going to do a substring and then I'm going
to start at the second character because there's a space in between the first character and the third
character there.
So, you know, index zero and then one is the space and then two is where we want to start our neighbors.
So I'm going to do that's going to be asked at length.
Minus one is what we go up to.
So it starts, starts at here or like for this example, I'm going to starts, say here and then goes
to here.
Cool.
So that will loop through and create our adjacency list by creating these keys, which are the first
one, and then it will have the neighbors as the value store to each one of those key indexes key hashed
indexes.
So let's now do the population of our visited.
So I'm just going to say, you know, the visited the same thing as Sub-Zero.
So it's organized by the vertex because, you know, this is the vertex of interest.
Is this first thing just to remind you?
So we're going to set these all to zero as we go through.
So that'll give us a visited where they're all just initialized to zero.
So after that, we just got a call depth for a search function, so I'm going to pass the first note,
so it's an unordered map is not in any specific order and I don't really care, but I'm going to do
the I'm going to pass it the first, the first value, like whatever that is, because we can start
it like whatever node.
And so I'm going to do that.
Like this, you do adjacency list and then it has a dot begin function for unordered map.
So that returns and iterator to the first item in the map and then key is the first and then the value
is the second.
So once you get a iterator to the first element in the map, you can then reference whether you want
the key or the value, and the key is the first.
And since it's a iterator, we've got to use the arrow like this for the pointer, and we're going to
say just first like this.
So that gets us the key of the first element stored in the adjacency list.
So, you know, just whatever starting node is, there is what we're going to start our research on.
And then, of course, I'm going to return zero and that.
Needed a semicolon there, so.
All right.
I think that is all that we need to do.
So.
Let's go ahead and.
Run this and make sure that my configurations are set up, so it has input, too.
OK, so input two is what we want because that is going to follow our graph over here.
So let's go ahead and print it out, we'll observe the output.
Of it, and then we're going to go ahead and head to this thing on the right, and we're going kind
of trace it and see, see what's going on there.
I'll have the code on the left and we'll look at the right and see what's going on with the stack frames
and all that.
So I'll go ahead and run it.
OK, so we have C A B D E F, so that is the order that it arrested in C, A B, D E and then F.
Cool.
So let's go ahead and scroll to the code here for a for search function.
And then let's take a look at this.
So I clicked actually here, which account to start right here.
So right off the bat, we are starting with C, so that's what's getting passed to this.
Depth, first search function, first past the node C, so see comes in right here and this vertex is
C.
And since we are on, since this is like this first call, it's going to be the first stack frames.
So this is the current stack frame we're on as sea.
So then.
We're going to print it out, so you see, if not visited, so see is not visited yet.
It's marked here, but we haven't visited yet.
It's the first node.
So you know, the marking is going to occur up here.
This yellow circle this time is not like us marking.
It is just to show you what node we're on in the graph.
This is going to be our visited container here.
So our visited map.
And that well, can you keeping track of what we have visited?
These are the stack frames.
And this is what's printing out the console.
So first thing to print out is see, just like we noticed here, know, see what's the first thing?
So it printed out.
See it said visited of see is going to be true.
So we set that to one.
So that's true.
And then we go down here and we go into our adjacent neighbors, so we have a and B.
And then so.
What happens next as we head to a.
So we're going to now that we're in a we're going to be in a stack frame, so basically we went down
here and we called the first thing that was in the neighbors.
A was the first thing that was in the neighbors.
We see like this right here.
So what that did was it said, OK, if a is not visited and it's not visited.
So we called desperate search recursively here, went back up with a cane at the top is not visited.
We just verify that here it printed out a now and then.
Now we are going to set a two visited.
So now is set to visited, we go down into this for a loop and we say, Hey, let's go through AI's
neighbors.
So we look at AI's neighbors, it's just like, see and be.
So if we go here.
A's neighbors C and B.
So it'll be on see and it said if not visited and called their first search.
But see is visited, so we're going to move on to the next one and that next one was B, as you saw
in here.
And so B would be B is not visited.
So therefore we can call depth first search on B.
So we will and now we had to be.
So now we're on a stack frame.
So we say, if not visited B, which B is not, is it if we're going to print it out, so we print out.
B then we market is visited.
We come down here, we look at B's neighbors, what it b's neighbors.
Well, it has a C and D, so we have c a d.
So it goes in here, it's on C.
Then it says the C visited.
Yes, it is a goes to a is a visited.
Yes it is OK.
It goes to D is d visited.
D is not visited.
Go ahead and call Deb for search with D.
So we had to d we now and d stack frames of the stack looks like this the call stack.
So now we're up here with Dee Dee is not visited yet to sell, it's printed out and now it's marketed,
the market is visited.
Then we're going to go through these neighbors.
So Dee has beef CBF.
So what we're going to do is Turn B B is visited, so we're not going to recursively call.
E is not visited, though, so we're recursively call and pass E.
So now we had to e we're on e stack frame.
E is not visited.
Printed out market is visited.
And then we go to ease neighbors.
Well, E has D and F. So we have the oh, that was actually sorry.
It's not if I don't know why, I said if they're so he just has the.
So we go here and it's basically going to be like, is here, but he is visited, actually.
So it's not going to call it recursively, and then it is the only sorry.
Andy is the only neighbor, so it looks at D and D is visited.
And so it's not going to call it recursively.
And since that's the only item in its list of neighbors, the fallout is going to finish.
And we're actually going to return and go to the previous stack frame.
So that's what's happening.
Look, we pop e off the stack, we go back to D. Now we're in the call for D.
So these stack frame and we're basically coming right back here because this is where we went into that
call for E!
So now we're here and so we're basically back on D and we're still in this loop because remember, E
was the first.
So actually, I'd be and it was like being all that's visited.
And then now we explored E!
And then we recursively came back.
And so the loop basically was left off on E!
And we passed E!
Now we came back from E!
And we still have f like there's still another item in that neighbors list f that we haven't visited
from D.
So now that we're back on DH, we basically go to.
And so that's what we're going to do is we're going to head to F..
Now we're on f stack frame because we called it and then so we look here.
F is not visited.
It's not in here.
So we're going to print it out.
We're going to market is visited.
We go here into its list of neighbors.
We see that it just has one neighbor, D.
And so what we're going to do is say, hey, is the visited, oh yeah, it is.
So we're not going to recursively call that it's the only neighbor to the for loop is done.
We return and we return back to DS and now we're on d d stack frame.
So we basically returned back to here, this function call right here because we passed F and then now
we came back from F. So now we're back here on D and we've exhausted that list for D.
So now the for loop is done.
So we return from that to the previous stack frame.
So we're returning to be and then you notice these are all explored, and so what's happening, we're
done with all these four loops, so we're going to return back to a from B.
Now we're on a stack frame.
We return back to see.
And then same thing, all of these have been explored as well.
We're done with the loop, so the loop is done.
You know, we're right here and then we're done with the loop for C.
So we return completely.
And we've done it all and we've printed it out and now we are done with the depth first search.
So that might have been a little overkill for some of you with the walk through, but I really just
wanted to make sure that if some people were still having some misunderstanding with the algorithm,
that this would clear it up if we really walked through with the code.
And this image right here, this animation.
OK.
So in the next video, we're not really sure what we'll be looking at.
We might look at the iterative version of this, or we might jump to breath research.
But either way, I will see you in the next lecture.