DFS Algorithm | Depth First Search Traversal in Graph | DFS Graph | DSA-One Course #76
DFS Algorithm | Depth First Search Traversal in Graph | DFS Graph | DSA-One Course #76
Hey guys, In this video, We’re going to Learn how Depth First Search Traversal Works using Recursion.
Practice: https://practice.geeksforgeeks.org/pr…
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Tags:
dfs
dfs algorithm
depth first search
dfs graph
dfs traversal
dfs in graph
depth first search algorithm
dfs algoritması
anuj bhaiya
graph data structure
dfs java
graph dfs
dfs in java
dfs in data structure
dfs of graph
bfs and dfs algorithm
dfs and bfs algorithm
graph traversal in data structure
graphs dsa
bfs dfs in data structure
graph traversal
depth first traversal
graph dsa
anuj bhaiya dsa
dfs and bfs
graph in data structure
graphs java
permutation in string
bfs and dfs
depth first search graph
depth first search java
depth-first search
dfs code
dfs in c
dfs in daa
graphs in data structure
algorithms
bfs algo
bfs algorithm
bfs algoritması
bfs dfs
bfs traversal
bridges in a graph
codehelp
d3.js
data structure
data structure graph
data structure tutorial
data structures and algorithms
deapth first search
depth first search in artificial intelligence
dfd
dfs algo
dfs c++
dfs dsa
dfs example
dfs in ai
dfs in python
dfs javascript
dfs search
dsa
dsa algorithm
dsa graph
dsa series
graph
graph data structure in java
graph graph
graph in dsa
graph playlist
graphs data structure
graphs in java
java anuj bhaiya
oops in c++
pre order traversal
python dfs
searching in data structure
tree in data structure
what is bfs and dfs
Content
0 -> Hey what's up guys Anuj here,
0.843 -> and welcome to the DSAone course,
1.548 -> in today's video we are going to talk about DFS.
3.897 -> Depth First Search.
4.76 -> This is also a traversal method like BFS,
6.671 -> there's DFS.
8.035 -> Both have their separate works,
10.204 -> both have different way of traversing.
12.125 -> Basically used to traverse in graph.
14.37 -> Let's understand how DFS works,
15.644 -> we've already seen BFS.
17.534 -> In DFS we go in depth,
19.615 -> like the name says Depth First Search.
21.368 -> That means go into one depth first,
23.436 -> until you went to depth and come back
25.759 -> and go to another depth.
27.051 -> This runs recursively, like we've seen in many trees,
30.329 -> we call in trees recursively,
32.71 -> whatever's the inorder preorder traversal.
34.975 -> First we go to one side completely,
36.922 -> after that we go another side,
38.657 -> we go to the full deep.
40.759 -> Whereas in Breath First Search,
42.383 -> there's a level order traversal
43.976 -> first you went here,
45.641 -> then it's next place,
47.121 -> then it's next place.
48.538 -> So first you travel a whole breath at once,
51.302 -> then travel the next breadth.
53.309 -> It's not like that here,
54.585 -> here you are going to the full depth,
56.012 -> then you come back and go to the next depth.
58.005 -> So here it is clear what's the difference in them.
60.258 -> There will be more differences as we see later.
62.341 -> Let's see how it works.
63.563 -> So let's understand how it works at a glance.
65.495 -> Suppose you start DFS from any node.
68.83 -> Here we started from 0,
70.497 -> so we will first go to 0
72.063 -> and call any of it's connected neighbours.
76.246 -> That are not visited yet.
77.558 -> So there's a visited concept in it too.
79.601 -> We know, we saw in trees,
81.174 -> when you are doing inorder traversal in trees,
83.33 -> then you know there you can go from parent to children
85.584 -> but cannot go from children to parent.
87.245 -> Because there's no way,
88.01 -> but there is a way here,
88.998 -> here you can go from 0 to 1 and from 1 to 0.
91.558 -> That's why we'll keep a visited boolean array.
94.235 -> When you visited 0, you marked it true,
96.919 -> that we have already visited here,
98.306 -> so we won't visit here again,
99.958 -> and any of 0's neighbour which is not yet visited,
103.312 -> go there,
104.72 -> and call DFS for it again.
106.774 -> So DFS is a function,
108.653 -> which we will call recursively.
110.736 -> So 1 & 4 are two neighbours of 0,
112.878 -> you can randomly choose 1,
114.358 -> we chose 1 the first neighbour,
116.035 -> so we'll come here and mark it true also.
119.335 -> Now which neighbour is 1 not visited,
121.802 -> so this neighbour of 1 is visited,
123.412 -> so we won't go there,
124.202 -> suppose we go for this 2,
126.272 -> and we mark true for 2.
127.426 -> So wherever you are going, also keep writing those values,
130.089 -> and this will be DFS traversal.
131.469 -> We went to 0,
133.149 -> then 1,
134.022 -> then 2,
135.831 -> after that which is the neighbour of 2
137.2 -> which is not visited,
137.994 -> this is visited,
138.871 -> 5 is not visited,
140.1 -> so we'll go to 5, mark true to 5,
141.963 -> and 5 will come here.
144.583 -> Next which neighbour of 5 is not visited,
146.808 -> 2 is visited, 6 is not visited,
148.854 -> so we'll visit it and mark it true.
151.539 -> After that from 6 we'll go to 3,
153.194 -> we'll also mark this visited,
154.451 -> and here we'll write 3.
155.993 -> After that which neighbour of 3 is not visited,
157.952 -> 6 is visited,
159.495 -> 1 is also visited,
160.598 -> but 4 is not visited,
162.366 -> so we'll go to 4 from 3,
164.13 -> and for this we'll call the DFS function again,
166.179 -> here we'll mark true.
167.296 -> Then we'll see which neighbour of 4, which is not visited.
170.295 -> 0 is visited,
171.726 -> from 4, 3 is visited,
172.825 -> so we'll backtrack from 4,
174.221 -> this will be backtrack.
175.518 -> Here we'll come back and see which neighbour of 3 is not visited,
178.831 -> so all the neighbours of 3 are visited,
180.929 -> that's why we'll also backtrack from 3,
182.808 -> here again the same procedure with 6,
185.133 -> 5, 2, 1, and then again at 0,
187.639 -> all of them, you can see, are visited.
190.579 -> Here we saw, we went all round and came back,
193.545 -> that is, we went to the depth of this graph.
196.62 -> We went to the depth of this graph,
198.793 -> this is DFS traversal.
200.297 -> If we compare it with BFS traversal,
202.385 -> you would do something like this in BFS,
203.814 -> you'll come here at 0,
205.531 -> after that we would put any two neighbours of 0
209.766 -> so we would put 1 and 4,
211.283 -> 1 and 4 would both get marked there
213.145 -> so we went to 1 and 4 from 0,
215.517 -> so you are following the whole depth at once,
219.738 -> we went to 1 and 4, then the next neighbour of 1,
221.883 -> which is 3, so we marked 3.
224.71 -> 1 also has 2 so we also marked 2,
228.195 -> we didn't go to 4 as it does not have neighbour.
229.563 -> Then the next after 2 is 5,
231.926 -> We marked 5,
232.826 -> the next of 3 is 6, so we marked 6.
234.705 -> In this way, there can be a BFS traversal.
237.391 -> One more thing to remember is,
239.033 -> there can be more than one traversals,
240.425 -> it's not important that this is the only DFS traversal,
243.527 -> there cannot be any other combination.
245.056 -> There can be another combination,
246.483 -> I told you to choose 1 randomly,
248.353 -> but if you choose 4 after 0,
250.568 -> then this would have been different.
252.099 -> Then you would go from 0 to 4 then 3, like this.
254.487 -> So it depends on you,
255.982 -> which way you are going with,
256.93 -> there can be different traversals,
258.405 -> if you apply recursive leap of faith,
260.002 -> there's not much to think about,
261.261 -> you just have think, if you go randomly to any node,
265.073 -> suppose to this node,
266.244 -> and I marked visited for this node,
269.275 -> that this is visited,
270.658 -> and all it's unvisited children,
273.771 -> all it's unvisited neighbours,
275.315 -> I called the DFS function for them again.
279.023 -> So you called for 0, 2, 3 again,
282.283 -> first you checked, which one of them is unvisited,
283.976 -> and for there you called the DFS function,
286.132 -> this is how it will work on its own.
287.904 -> So, it's very simple,
289.492 -> it's easier compared to BFS,
290.791 -> because it is done recursively,
291.877 -> you apply queue in BFS,
293.449 -> here you apply stack,
294.934 -> there was no need for stack here because recursion already gives you a stack.
299.2 -> If you are told to do it iteratively,
300.619 -> then you can also easily do it iteratively,
302.808 -> just like you were using queue in BFS,
304.089 -> similarly you can use stack here.
307.039 -> This will become DFS automatically.
309.318 -> We first have to take care of a visited boolean array,
311.667 -> after that it all works.
313.499 -> Now let's see how it's code will work,
314.967 -> and after that there are some little differences between them
317.39 -> between BFS & DFS,
318.422 -> we'll understand them.
319.06 -> So we'll see the code here,
320.496 -> the code will similarly remain like I taught you.
323.067 -> We are going to code the same thing,
324.831 -> we have a function named dfsofgraph,
326.651 -> now we are given the no. of vertices
329.059 -> and an adjacency list,
331.944 -> which is representing the graph.
333.814 -> But we know, when we will be calling this function
336.032 -> then we'll also need some other things in this function
338.441 -> like for which function is this vertex being called,
341.042 -> that vertex and apart from that
342.408 -> we would also need visited boolean array.
344.692 -> Apart from that, this function is telling us to return
346.398 -> array list of integer.
347.43 -> Which is the DFS traversal of this graph.
349.379 -> So we will also pass this in the function
351.43 -> So we would have to create our own recursive function in this.
354.388 -> For that we would require some things.
355.844 -> We'll add them,
357.118 -> first of all will be the visited boolean array,
358.893 -> visited boolean array whose length will be equal to its vertices,
362.704 -> like from here, it is starting from 0,
364.208 -> you have to see in your graph, how the graph is starting,
367.262 -> my graph is starting from 0, that's why I'll say the boolean array
370.414 -> of the no. of vertices here will be enough for me.
373.753 -> If your graph is starting from 1, then you should create the boolean array with v+1,
378.866 -> because your graph is starting from 1.
380.928 -> Because of indexing.
382.241 -> After this, the next thing,
383.433 -> we'll create an arraylist of integers answer,
385.966 -> because we have to finally return this answer,
387.777 -> and this answer will be passed in the DFS function.
390.647 -> So this is the dfs function,
392.253 -> now, how this dfs function is working,
394.327 -> and how the answer is added in this, we'll see.
397.366 -> First let's return the answer from here,
399.099 -> and this is the dfs function.
401.005 -> Now let's understand this function, what's happening here.
403.08 -> In this function, we passed vertex
405.547 -> for which function the DFS function is being called,
408.049 -> after that array list of array list of integers
410.74 -> this is the adjacency list, this is the actual graph
413.395 -> after that the boolean visited array,
415.574 -> and after that the answer.
417.161 -> I am also passing the answer in this.
418.916 -> So these are some values, which I cannot pass in the above function,
421.844 -> that's why I had to create another function.
423.805 -> And you do this quite often.
425.33 -> When you solving the questions by calling recursively.
429.107 -> So we'll start, first of all
430.522 -> first we'll say that for this vertex the DFS function is not called yet,
436.362 -> so this has vertex has not been called yet, this vertex has not been visited yet,
440.532 -> so first we'll visit true for this vertex,
443.681 -> so we did visited true for this vertex,
446.492 -> after that we'll also add this vertex in the answer,
449.384 -> so answer.add vertex,
451.083 -> we put this vertex in the answer,
452.341 -> now what we'll do is,
453.306 -> from this vertex, suppose it was vertex no. 0,
456.183 -> from this vertex, we'll run for loop all the connected neighbours
460.914 -> so this is the for loop,
462.542 -> so for evert neighbour, in this adjacency.get v.
466.772 -> So, all the neighbours of 0, 1 & 4,
469.08 -> for both of them the for loop will run,
470.554 -> and for these two we'll call the DFS function recursively.
474.907 -> So here, first of we'll check which vertex is not visited,
479.523 -> which neighbour is not visited,
480.841 -> so we'll see for 0,
481.943 -> 1 & 4, suppose we go to 1 first,
484.461 -> so 1 earlier was not visited, 1's visited was false,
487.071 -> so we called for 1.
488.906 -> So we'll call here,
490.771 -> and in this way we are calling, DFS of neighbour
493.684 -> and we passed all the other things just like this.
496.326 -> So this was a very simple code, you can see,
498.718 -> this function will keep running on its own,
500.992 -> it will work just like we saw, let's once again try run it on an input
505.194 -> so that you understand the whole code clearly.
506.695 -> Suppose this is the example,
508.573 -> in this example we have to start DFS from 0
511.994 -> it is given in the question to start from 0,
513.858 -> how many vertices do we have,
514.933 -> one, two, three, four,
516.883 -> we have four vertices, so V is 4.
519.03 -> So we'll make a boolean array of this size,
521.077 -> which is called visited.
522.271 -> And this will the answer array list,
523.922 -> this will be the array list where we'll store all the answers.
527.715 -> We'll start, from 0,
529.473 -> so this is the first vertex, we'll call from here,
531.759 -> first we'll mark this true,
534.014 -> it's visited will become true,
535.348 -> earlier this would be false by default,
536.96 -> we marked this true,
538.108 -> so this is now true.
539.277 -> Now for 0 it has been called,
540.806 -> what we'll do is put 0 in the answer,
543.535 -> so we put 0 in the answer,
545.172 -> Now it's neighbour, we'll call for them, we'll go to the for loop
548.397 -> first here DFS of 0 was called,
551.051 -> I called dfs for 0,
553.282 -> this 0 is the vertex number,
554.982 -> suppose from dfs of 0 you called for dfs of 1,
558.017 -> because for 1 it is false right now,
560.039 -> so from here we called for dfs of 1.
565.237 -> Now we'll go to 1,
566.488 -> and mark true for 1.
568.644 -> So this will be marked true for 1.
569.972 -> Now we'll go to 1's neighbours
571.095 -> and we'll also put 1 in the answer.
573.277 -> We'll go to 1's neighbours, 1's first neighbour is 0
575.787 -> but it is already true for 0, so we won't call for this
578.435 -> 1's next neighbour is 3, for 3 right now it is false here,
581.463 -> so we'll call dfs for 3, call from dfs 1 to dfs 3.
587.555 -> And when it will be called for 3, we'll mark 3 true,
591.096 -> and after that we'll also put this 3 in the array list.
593.728 -> After that we'll call dfs for neighbours of 3,
598.247 -> 3's next neighbour is 1,
599.452 -> but it is already true for 1, so we won't call for 1,
601.684 -> there's no other neighbour of 3,
603.774 -> so from here 3 will go back, it will backtrack,
606.591 -> we have came back to dfs 1 from dfs 3,
609.389 -> we have control over dfs 1 again,
610.89 -> it will go to its for loop, it'll see which next neighbour is not visited,
613.878 -> the next neighbour it'll find is 2,
616.165 -> 2 is not visited, so it will call dfs for 2
618.42 -> it will call again, this time for dfs 2.
623.319 -> We'll go mark true for 2.
625.748 -> We'll put 2 in this array list.
627.424 -> And after that whichever neighbour of 2 which is not visited
629.727 -> we'll call for it,
630.97 -> but you can see all the nodes are visited,
632.877 -> so the for loop for 2 will be exhausted and nothing will be left,
635.535 -> so from 2 it will go back
637.766 -> again to 1 call,
639.324 -> the call will go from 2 to 1, and 1's for loop is also exhausted,
642.633 -> so from 1 the call will go to 0,
645.562 -> and even 0 doesn't have any such neighbour, because 0's first neigbour was 1,
648.32 -> but 1 was visited, we came back from 1,
650.753 -> next neighbour is 2, but 2 is already visited
652.732 -> so there won't be a call again from 0 to 2.
654.571 -> And we'll get out from here,
656.957 -> and in the answer will remain, 0, 1, 3, 2.
659.116 -> This is the dfs traversal for this graph.
662.089 -> I hope you understood it all,
663.419 -> how it is working.
664.376 -> Now there can be one other thing here,
666.024 -> this is the connected graph
667.533 -> in the question you are given,
669.663 -> Given a connected undirected graph.
672.539 -> but it may be that the graph is not connected,
674.796 -> maybe your graph has some disconnected components.
677.98 -> This is 0, 1, 2, 3, 4
679.069 -> suppose you have something like this between 4 and 5.
682.826 -> There's another disconnected component.
684.707 -> So when you will call DFS for this,
686.109 -> then you never called dfs of 4 or 5.
689.26 -> For them, this array list,
692.52 -> will remain empty here,
694.988 -> false will still be here.
697.429 -> And in the answer there won't be 4 and 5.
699.933 -> This can happen,
701.164 -> what you'll do is, you
702.027 -> I've told you this in BFS too,
703.313 -> what you were doing there is running another for loop,
705.489 -> and for that for loop, we were seeing which is the next false value
708.991 -> and for that you'll call the DFS function.
712.383 -> So we will be doing the same thing here,
713.816 -> let me tell you in the code.
715.053 -> We don't need to change anything in below function
717.408 -> simply from where the function is being called,
719.298 -> is where the changes will be.
720.647 -> First we were calling the dfs function with initial vertex 0,
724.112 -> now we'll call for every vertex which is not visited yet,
727.475 -> for that we'll run a for loop,
729.316 -> this is that for loop,
730.849 -> for int i equals to 0, i less than v,
732.902 -> we'll run for all the vertices,
734.274 -> and keep checking if the vertex is not visited yet,
737.916 -> if i'th vertex is not visited yet,
739.817 -> then for this i'th vertex, call the DFS function for this.
742.93 -> So this is how the DFS function will be called now,
745.071 -> now for this, we'll comment it.
747.158 -> You will call this function like this,
748.94 -> and now for all the disconnected components
751.456 -> dfs will be called automatically.
753.951 -> When you called for this, for 0,
756.19 -> this is will be done,
757.709 -> after that you'll run the next,
759.571 -> the for loop will run again,
760.713 -> it will go to 1 from 0,
761.708 -> but for 1 it is already visited,
762.835 -> so, skip,
763.454 -> visited for 2, visited for 3,
765.073 -> it is not visited for 4,
766.735 -> for 4 it will be not visited.
768.632 -> For that we'll again call the dfs function,
770.869 -> now dfs 4 will be called,
774.424 -> dfs 4 will be called, from dfs 4 dfs 5 will be called,
778.405 -> and this will mark these two true.
780.435 -> So this is how you will travel all of them.
784.624 -> And that's how you can also count the no. of connected components,
788.263 -> with the help of BFS you can count the no. of connected components.
791.282 -> And using DFS too.
794.74 -> We'll will be using DFS in multiple places
796.61 -> in the upcoming videos.
798.032 -> This was it for this video,
798.95 -> if you enjoyed the video,
799.842 -> Like it, Subscribe the Channel,
I'll see you in the next video.
803 -> Bye, Bye!
Source: https://www.youtube.com/watch?v=0ql7lZS2qt0