Depth First Search (DFS) Explained: Algorithm, Examples, and Code
371,848
Published 2020-07-05
0:00 Intro and Preview
0:50 Graph Traversal
1:20 DFS Walkthrough and Examples
6:26 Recursive Implementation
11:08 Iterative Implementation
15:06 Preorder vs Postorder DFS
17:01 DFS Applications
Support: www.patreon.com/reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
All Comments (21)
-
This is how I explore caves in Minecraft.
-
The thing I love most about great channels using manim, is that i never feel like im watching a 3B1B rip-off, just an intelligent explanation of a topic. Keep up the amazing videos
-
By the way, a very interesting point is that you can convert any recursive function into a stack + while len(stack) > 0 loop because basically that's exactly how computers do that on a low level anyway. In some languages it has some advantages, because while function call stack may be limited, a stack as a structure is practically unlimited, and that lets us achieve very deep levels of recursion without stumbling into stack overflow.
-
This is the best video on this! I love this channel, it is going to become really popular! Thank you! Love the animations. And the design.
-
One thing that I love about this channel is that, because the quality is so huge, all the comments will start praising the video but also adding new information and providing constructive feedback. I think that people feel compelled to give some retribution after watching such a great video for free.
-
great video! I'll also point out (as a few others have hinted) that the iterative approach is very important for large graphs. Default stack sizes on modern OS' are still typically quite small, and it's easy to construct pathological graphs which will cause a stack overflow with a recursive DFS implementation. Using an explicit (and heap-allocated) stack as in the iterative approach works around this (until the machine runs out of memory, of course!), and is a crucial reason why this approach is often chosen.
-
i can feel your effort man, the planning, research, animation, music.. I'm glad i came across this channel.... you gonna get huge success..
-
The presentation of how to use a stack and pop together was really interesting. I always had trouble with while loops, this pattern makes it so apparent when it is best used.
-
Your content is incredibly good. It's not only comprehensive and to the point, but also enjoyable. Thank you for all the effort you are putting in.
-
This was a great video, explaining not only DFS, but both recursive and iterative versions of it, and presenting applications for DFS, all accompanied by illustrations to make it even more clear. Cant thank you enough!
-
The best CS channel to understand graphs hands down! THANK YOU Reducible!! You are just awesome!
-
Thank you for making DFS and BFS understandable. Simple and on point
-
I really love your explanation, it's short, concise, easy to understand, straight to the point. I watched many another's videos, they were lengthy and hard to understand.
-
I love 3B1B videos and now these are my favorite too. Thanks for all the effort and excellent explanations!
-
The video is great, as always. However, I have a suggestion: maybe at the end of the video, you can ask some graph questions and let us think how to slove, and finally, you can give the java or python code and the step of it. (just like your recursion video because your recursion video is absolutely amazing.)
-
absolutely the best explanation on DFS that I have encountered. Please make more videos on graph theory and algorithms.
-
This is the best way to explain recursive functions to newbies like me. Thank you so much for such great contents.
-
Well structured, easy to follow, beautiful graphics, use of video chapters and real world use cases included. What can I expect more? Superb video.
-
You deserve so many more subs. This content is so well explained. Fantastic channel!
-
probably the best explanation of DFS I have ever come across! thank you! :)