so in this video we are going to learn about the second traversal technique that is the dfs traversal in a graph now in the previous video you did learn about something which was bfs breadth first search which was based on level now we will be learning as dfs which is depth first search now this will be based on depth depth depth yes so why did i emphasize so much on depth you'll understand again similarly you'll be given a graph and you'll be given a starting node assume the starting node to be one over here okay the starting node is one this is one okay now you go to any one of the neighboring notes two three four any one you can go so for example i decide i will go from one to the left neighboring node which is two so if you go to two you don't stop there very important you start it from here you go here and then you don't stop stop you go depth depth so you go to depth which is five again you can either go to here or here that is your choice but generically we go to the guy who is right uh at the first of the adjacency list or from left to right so five will be there so you basically go like this so it's like one two five done now you've gone like one two five there is no further depth in it so what you do is you come back and now you go to here which is the six which is the six so you go to six right now you went like one two five you came back you went to six now there is no depth of six so you come back now there is no further children of two so you go back now once this portion depth is completed right starts going to the next portion which is three so you go to three done now when you've gone to three now again either you can go this way or you can go this way that is your choice so i decide i'll go this way so i'll go like seven i'll go like seven okay so i go seven no like one three seven now seven's depth is eight does not needs to be down neighbor seven seven's depth is eight so you go to eight eighths depth is four so you go to four so apparently you started from one you came to three you went to seven you went to eight you went to four and after that you can't go because this is already done so you go back there is no further go back no further go back no further go back suddenly this portion is done had there been assume had there been someone else something like three four nine ten then coming back you'd have gone to nine ten so you go to depth you go to depth at first i hope that makes sense so this will be the dfs this will be the dfs again it's not necessary that you go like this this then this you could have done the other way like one three then you could have gone like this four eight seven then you could have gone to two then to six then to five you could have done that way that is as long as you're traversing in depth any traversal type will work but it should be depth depth okay so let's uh change the starting node in order to understand the dfs traversal more okay so assume i change the starting node to be somewhere around three now assume this is the starting so again this will be the first point for sure this will be the first point now from three you can either go here you can either go here you can either go here your choice so i decide i'll go to four from three i decide i'll go to four so it'll be like four then you'll go to eight then you'll go to seven so be like three four eight seven so three four eight seven so three twenty four four one two eight eight twenty seven cannot go further comes back comes back comes back so this portion depth is completed depth is completed now go the other way which is one so you go to one you go to two again do the same thing five and then six are the opposite it's like one two five six now come back again now three will it go to seven no because seven has already been covered so if you start from three and you go in this then you go in this this will be the dfs there can be plenty of dfs depending on the starting node yes depending on the starting node and which algorithm if i ask you which algorithm usually goes to the depth solves it comes back yes use said that correctly recursion that is absolutely correct the algorithm that always goes in depth like if you remember this kind of algorithm is do you remember this kind of algorithm is nothing but recursion and if you have not seen the recursion playlist i will highly recommend you go back and watch my recursion playlist at least till video seven at least from video one to video seven because entire graph without recursion will be nightmare you need to understand how graph works in dfs traversal otherwise it will be a big big mess so again for this graph where do you store that you store this graph in an adjacency list that is something which you will do so please please go and store this graph in an adjacency list so this is how the adjacency list for this particular graph will look like now assuming uh the starting node is given as one okay assume the starting node is one what will be the initial configuration again similar to bfs travis you will first create a bfs so uh first create a visited array again please go and check if it is a one b's indexing so if you see a one based one to eight so please create like a nine size array zero one two three four five six seven eight so a visited array is what initially you will start off with and whatever is the starting node just mark it as visited and everything else will be staying as zero similar to what we did in bfs done what will be the next step remember this the next step is going to be whatever is your starting you call a recursive function remember this you call a recursive dfs function from that okay now what you will do is this dfs of one i like the code somewhere df is up node what this will do is the moment it gets into the function it states hey dude listen this guy is done and this is a part of my dfs well you can just add a list and you can say this is a part of my dfs okay so this is the line where you will do the dfs traversal because you are visiting a note so stored now what you do is remember this what you do is you went to one now either you can go to two either you can go to three you go this depth or you go this depth so you travel the neighbors either you travel two first or three first that is your headache but you travel the neighbors at first so how do you travel the neighbors of one very simple they store in the adjacency list if you carefully see they stored in the adjacency list so for any node you go to their adjacency list you go to their adjacency list right so this is nothing but adjacency of one so this is the vector this is the list so that is what you'll pick up that is what you'll pick up so pick up the list and run a for each loop in it so this these are the neighbors run a for each loop in it adjacency of node so this is the list of neighbors and you're running it and now you go depth by each node so first you go to the depth of two then you go to the depth of three so first go to the depth of one i t which is one neighbor and in the next iteration the next it will go so imagine this to have two comma three what will happen first a call of two will be made so it'll be like dfs of two is made then when this completes the call completes because it is a recursive call it's a recursive call when it completes then it goes through the dfs of three you need to understand this okay so it's basically something like okay uh let's get back is something like okay first we have to let's call the dfs for two it will go and it'll complete like go to the depth depth depth depth and then come back then the next guy will be three then it will go to the dfs of three and then come back so it's like dfs of two will be performed in depth then dfs of three but you don't visit every time all the notes because when you go to two it will have the neighboring as one five six but from two you will not go back to one from two you will not go back to one so it's very important a node which has been visited in its traversal you don't visit it again so what you do is you say okay listen this node has to be unvisited for me to go into the depth of it this node has to be unvisited for me to go into the depth of it simple so this will be the simple lines of code that you need to execute so what will happen is dfs of one will come i will mark it as visited now it has two neighbors two and three so we'll go to the depth of them right so for two it again goes and checks there is one but that is already visited then there is five and then there is six so it will go for both dfs for five and then dfs for six so how is the call coming up first the call was for one right so you can write one next the call went to two right next the call went for five so number five when you go to five remember this by the way when you go to two you'll mark it as one now you go to five mark it as one number five what happens is see here for five the neighbor is two which is already marked there will be no further calls so if i will say there are no further calls there are no neighbors so i don't call anyone so i will come back i came back right now dfs of 2 goes to dfs of 6 6 says do i have neighbors i do 2 which is already visited no further calls comes back now two says do i have any other neighbors apart from five and six no i go back one so two is completed so initially when you started with two it is completed now the next guy three will be occurring next guy three will be occurring so you go to three now three is marked as visited and now you're traversing three so the next we go to dfs of three so let's check out who are the neighbors of three so the neighbor of three appears to be four and seven so first we will go to four then we'll go to seven but apparently what will happen is when you go to four four in turn will go to eight eight will go and turn to seven so four when it goes to depth it will visit seven so thereby this call was made depending on where four lies on the adjacency list we made this call if there was something like 7 4 you would have gone like this so it depends on the adjacency list which format like which traversal you will traverse okay so for three who are the neighbors one no four and seven four and seven first we go to four perfect let's go to four then we will think shall we go to seven or not then we will think shall we go to seven or not we are not sure as of now but give us a full shot let's go to four market is visited and four is there perfect now let's go to four who are four sleeple there should be three and eight three is already visited but eight is not so let's go to eight very simple again if you're going to wait market is visited at the moment you go to eight who are eight neighbors four no need to go seven okay interesting let's go to seven and seven is visited now who are seven stable three and eight those guys are already visited you've already traversed them so you do not go you do not go yes you do not go so apparently seven is done seven says i don't have anything my recursion is done can he just go back he's like okay let's go back it says i don't have any neighbors can you please go back says okay who says i don't have any neighbors can you please go back yes so this three this three went into one of its neighbor four will it go to the next neighbor seven no because seven was visited by this part there is no need to again go and visit seven so this supposed neighbor is no more visited thereby the tfs is this portion this is your dfs call so if you carefully observed from here whether you went like this or whether you went like this dependent or was dependent on the adjacency list so i hope you've understood the technique that's time to check out the code so as usual in the code so the c plus plus code is what i'll be typing and on the left you can see the entire java code in the similar format so you can just follow the java code and you can understand every line while i type the c plus code the syntax is almost identical so what do we have we have the number of nodes and the adjacency list you don't need to create the graph because that is always given to you so if you carefully observe it's a connected undirected graph and it says the starting index is zeroth vertex so something to observe it's a zero based indexing graph so this will do right perfect so starting index is zero so you can say the start is zero i need to store the so you can create a list in order to uh store the dfs ls okay so over here you can go back and say cool private and right here what you can write is void dfs this will be the note correct you need uh this particular adjacency list so please carry the adjacency list as well and what is the next thing that you need you need to visit it so please carry the visited and you need the list which stores the particular dfs so please carry the list as well now what will you do when you enter so the moment you enter you remember this is mandatory and you add it in the you add the node into the vector or the list what's the next step the next step that you do is you travel for all its neighbors this is how you traverse for all its neighbors whatever this this is the way in which you traverse all its neighbors okay so now what is the first thing that you do if this neighbor is non-visited very very important if this neighbor is non-visited you call dfs it adjacency visit and just pass on the parameters and this is how the dfs will be and over here what you do is you call the dfs the starting node the starting node can be anything pass on the adjacency pass on the visited pass on the ls once the entire dfs has been completed you return the ls and now you can just go and compile hopefully it runs so if you see visited of n okay as usual our common mistake this will be if you see the output is correct uh let's quickly submit this so internally the code has also been written in such a way that it follows the adjacency list so you don't need to worry the code will be working fine but this is what is the dfs traversal of a graph so let's talk about the space complexity so what will be the space complexity how many nodes are we visiting at max we are visiting n nodes in our traversal so we can say that we are storing n nodes in those dfs transit we are using big o of n for visited and the recursion stack space are the worst case because what is stack space if you remember recursion this is the stack space so the worst case if i give you a graph like a skewed graph you will end up going like one two three four so the recursion stack space at the worst case can be of n so i can call it near about we go often if you do not include the adjacency list what about the dfs travis so how's the dfs traffic it's a function and then it iterates on the neighbors right i trades on the nipples and for every neighbor it calls the function this is how it is right so this function will always be called for a single node this function will always be called for a single node right and any node for any node it will just be called once because you traverse a node single time for node one it will come once for node two it will come once and for every node we will have a certain number of neighbors that it is iterating it is i trading so can i say for an undirected graph can i say for an undirected graph these neighbors for 3 the neighbors are 1 7 and 4 which is the degree of the graph which is the degree of the graph can i say it is the degree of the graph like sorry degree of 3 yes and for every node can i say it will be the summation of degrees so can i say it will be the summation of neighbors or the summation of degrees i can say summation of degrees because for every node it will be the number of neighbors plus number of neighbors plus number of neighbors which is equivalent to degree of a node plus degree of a node plus degree of a node which is equivalent to summation of degree right so what is the summation of degree if you remember the first lecture that is 2 into number of edges and then for every node you're calling the function once so we go of n for calling the recursion once so this is the time complexity for an undirected graph for a directed graph it will depend on the number of edges so this two will go off and the number of edges is what it will boil down to so guys i hope you have understood the entire explanation as well as the code and the time complexity in the space complexity just in case you did please hit that like button and if you're new to our channel what are you waiting for hit that subscribe button right away with this i'll be wrapping up this video and yeah for the dp series and the sd sheet you can find the link in the description make sure you check it out and let's wrap up this video let's meet in some other video don't ever forget