Depth First Search (DFS) Explained: Algorithm, Examples, and Code

In this video, I explain the fundamental ideas behind the Depth First Search (DFS) graph algorithm. We first introduce the concept of a graph traversal. We then go through several examples of DFS to provide intuition. Afterwards, we then go through both a recursive and iterative implementation with provided code. We discuss the differences between the implementation and also make a distinction between a preorder and post order DFS traversal. We then finish the video off with some practical and fun applications of depth first search in graph theory.
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: / 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

Пікірлер: 297

  • @hetsmiecht1029
    @hetsmiecht10293 жыл бұрын

    This is how I explore caves in Minecraft.

  • @abhishek.rathore

    @abhishek.rathore

    3 жыл бұрын

    I had the exact same idea. Lol ;)

  • @zuhairmehdee

    @zuhairmehdee

    3 жыл бұрын

    This is a surprisingly intuitive comparison. Thanks a lot. +

  • @ElektrykFlaaj

    @ElektrykFlaaj

    3 жыл бұрын

    except caves in minecraft often have no dead end

  • @abhishek.rathore

    @abhishek.rathore

    3 жыл бұрын

    @@ElektrykFlaaj yeah and they often loop back too

  • @ironlegnebula

    @ironlegnebula

    3 жыл бұрын

    +1 best system, would recommend

  • @jamesmarx1144
    @jamesmarx11443 жыл бұрын

    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

  • @ejejej9200
    @ejejej92003 жыл бұрын

    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.

  • @Reducible

    @Reducible

    3 жыл бұрын

    Thanks for the kind comment!

  • @mikumikuareka
    @mikumikuareka2 жыл бұрын

    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.

  • @thefamousdjx

    @thefamousdjx

    7 ай бұрын

    Wow thanks this made me dig deeper and understand even better.

  • @ferrisstreamsstuff
    @ferrisstreamsstuff2 жыл бұрын

    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.

  • @marioivanovivanov4248

    @marioivanovivanov4248

    Жыл бұрын

    Hi can u please tell me more about this? For example how is it possibile to construct a "pathological" graph. i'm assuming that a pathological graph is a graph whose nodes are linked in such a way that when the DFS algorithm is called on the graph, it goes into an infinite recursive loop that overflows the stack.

  • @alex0917lfo
    @alex0917lfo4 жыл бұрын

    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.)

  • @Reducible

    @Reducible

    4 жыл бұрын

    Thank for the feedback, will try to incorporate more problems in future videos.

  • @hanshima_
    @hanshima_2 жыл бұрын

    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.

  • @Saurabh1369
    @Saurabh13693 жыл бұрын

    i can feel your effort man, the planning, research, animation, music.. I'm glad i came across this channel.... you gonna get huge success..

  • @fulgren0965
    @fulgren0965 Жыл бұрын

    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.

  • @irina1nik
    @irina1nik3 жыл бұрын

    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.

  • @dorian0623
    @dorian06233 жыл бұрын

    Well structured, easy to follow, beautiful graphics, use of video chapters and real world use cases included. What can I expect more? Superb video.

  • @EmadGohari
    @EmadGohari3 жыл бұрын

    I love 3B1B videos and now these are my favorite too. Thanks for all the effort and excellent explanations!

  • @StellahRotich
    @StellahRotich2 жыл бұрын

    Thank you for making DFS and BFS understandable. Simple and on point

  • @aminforoutan6065
    @aminforoutan60653 жыл бұрын

    absolutely the best explanation on DFS that I have encountered. Please make more videos on graph theory and algorithms.

  • @navneet5084
    @navneet50843 жыл бұрын

    The best CS channel to understand graphs hands down! THANK YOU Reducible!! You are just awesome!

  • @haitu8896
    @haitu88962 жыл бұрын

    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.

  • @conall5434
    @conall54343 жыл бұрын

    You deserve so many more subs. This content is so well explained. Fantastic channel!

  • @hayk.galstyan
    @hayk.galstyan8 ай бұрын

    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!

  • @henrythai2020
    @henrythai20202 жыл бұрын

    This is the best way to explain recursive functions to newbies like me. Thank you so much for such great contents.

  • @kensword
    @kensword4 жыл бұрын

    looking forward to BFS too! Thank you for posting!

  • @hemantmangwani7172
    @hemantmangwani71724 жыл бұрын

    Great Content Man and that Recursion video is Awsome . Keep Making more videos.

  • @shahidahmads
    @shahidahmads3 жыл бұрын

    probably the best explanation of DFS I have ever come across! thank you! :)

  • @TheAmberZhang
    @TheAmberZhang Жыл бұрын

    Best video so far I found on DFS algorithm. Very clear explanation. Thank you very much!

  • @vijaykumarreddyalavala3713
    @vijaykumarreddyalavala37133 жыл бұрын

    I'm proud for being among the first 1000 subs while I know this channel will explode subs count to millions very soon

  • @ejejej9200

    @ejejej9200

    3 жыл бұрын

    Me too! This channel is going to be huge!

  • @curbyourshi1056

    @curbyourshi1056

    3 жыл бұрын

    It's absolutely happening. Pleased to be part of the blow up.

  • @montehatch
    @montehatch2 жыл бұрын

    These videos are gold. They go into much more depth than their peers, with expanded intuition, alternatives, and application. Well done sir! P.S. the animation is also top notch.

  • @vibhor3049
    @vibhor30493 жыл бұрын

    Brilliant video. Those animations really helped to understand the whole process. Thanks!

  • @zamoqi
    @zamoqi3 ай бұрын

    Your videos make the difficult concepts so easy to grasp!

  • @nadiakruger4206
    @nadiakruger42062 жыл бұрын

    So happy I found this channel and this video! It was really, really helpful.

  • @Latesttechs
    @Latesttechs3 жыл бұрын

    Amazing video I have already done my bachelors in CS and have seen various videos explaining various Algos but your approach is simple, intuitive and precise among all others please keep it up!

  • @abanerjee3704
    @abanerjee37043 жыл бұрын

    I couldn't help myself but comment how beautifully the content has been delivered..... Kudos to u guys, love and appreciation from India🤘🤘

  • @codewithsimran9899
    @codewithsimran98992 жыл бұрын

    This is Gold! Just one video and I think I'm done understanding graphs. Thanks a lot!

  • @thamidurandilbandara415

    @thamidurandilbandara415

    Жыл бұрын

    there is a lot more, but yes the video explained it very well

  • @yuriymelnykov1464
    @yuriymelnykov14643 жыл бұрын

    Thank you for the amazing video. This is the most understandable explanation I've ever seen. Visualization, narration and music is very good:)

  • @sdk-yourfriend1561
    @sdk-yourfriend1561 Жыл бұрын

    Great video, great teaching, and great animation used here to make things understandable by going into a deeper level of abstraction of all the steps and processes. Before this video, I watched 4-5 videos on DFS that appeared on top after searching and had more views (even in millions) but couldn't understand them clearly. After all, this is the ultimate video that quenched my thirst. Thank you sir for your great content. This channel should grow more and more fast.

  • @anbesivamkamal
    @anbesivamkamal4 жыл бұрын

    Simple and Clear:) Thanks for the amazing videos!

  • @tanvitanvi4235
    @tanvitanvi42353 жыл бұрын

    This is the first time I'm posting a comment for a video, simply because I don't really bother to. But this is something. This is that good! Sooooo good! Concise and yet complete. Simply brilliant!

  • @aakankshaagrawal223
    @aakankshaagrawal2233 жыл бұрын

    JUST WAITING FOR THIS WONDERFUL WONDERFUL GEM OF A CHANNEL TO EXPLODE. THANKYOU THIS IS AMZING

  • @raunakmitra7868
    @raunakmitra78682 жыл бұрын

    2:22 is an example of the classic Cycle Detection algorithm where DFS is used to detect any cycle in a graph G. Child node 2 has a "back-edge" that connects it with the root node 0. This is basically a cycle in the graph.

  • @nicholasziglio
    @nicholasziglio2 жыл бұрын

    Brilliantly explained, so simple and clear. You gained a new subscriber!

  • @shwetamishra3591
    @shwetamishra35913 жыл бұрын

    It's really amazing... your contents and way of explanation everything is awesome... keep it up...

  • @goldenlin9528
    @goldenlin95282 жыл бұрын

    great animations, video, and i love the last part where u mentioned the applications

  • @wolfy_pride
    @wolfy_pride9 ай бұрын

    Amazing!!! Please do this for all concepts of DSA. You are a rare gem!!!

  • @vaibhavsomani2690
    @vaibhavsomani26902 жыл бұрын

    Thanks for that soft music in background, really helped boosting focus while watching this video. Great explanation as well. Thank you.

  • @MD.MamunUrRashidHridoy
    @MD.MamunUrRashidHridoy2 ай бұрын

    The way we designed the animation and the calmness of your voice in the time of explanation and the depth of your discussion just blow my mind. May Almighty Bless You💝

  • @nerodant85
    @nerodant85 Жыл бұрын

    I really love your format, great work, subbed right away

  • @yeah5037
    @yeah5037 Жыл бұрын

    Loved your amazing explanation, thank you!

  • @fernandocelso8332
    @fernandocelso83323 күн бұрын

    What an incredible video, thank you for the content, really well explained! 😁

  • @redtree732
    @redtree7327 ай бұрын

    Okay, I'm 5 minutes in but I had to comment. This is, hands down, the best explanation of DFS I've ever encountered. Thank you so much for this phenomenal video - I hope you keep it up!

  • @priyankareddy7408
    @priyankareddy74083 жыл бұрын

    thank you so much for the amazing explanation and such great animations!

  • @moosegoose1282
    @moosegoose12822 жыл бұрын

    this is probably the best explaination ive came across

  • @xsYlarx1
    @xsYlarx13 жыл бұрын

    Best video ever. Helped me understand the DFS better.

  • @ferroumsamir6531
    @ferroumsamir6531 Жыл бұрын

    you do great job. you deserve more appreciation, and you will have it.

  • @elifsuates4151
    @elifsuates4151 Жыл бұрын

    Perfect explanation. It is may 5th video and just understood everything thanks to you. Great.

  • @jrub3314
    @jrub33143 жыл бұрын

    You get a new suscriber! Amazing videos and explanations! Really really very good!

  • @sher.5027
    @sher.5027 Жыл бұрын

    I liked and subscribed. awesome explanation. Good visualization and best animation. Keep the good work.

  • @tejasnakhate
    @tejasnakhate3 жыл бұрын

    I wish this videos came earlier.....great content man!

  • @ravitiwari1686
    @ravitiwari16863 жыл бұрын

    Great Effort there! Appreciate the time you took to fork Manim and manage it so well for all of us. Regarding the algo in preview, at 8:20, where you mention to maintain boolean values of marked nodes, it should be of size/length - G.order() rather G.size(). For a graph, order = number of vertices = |V| while size = number of edges = |E|. This could cause problems if we have a straight line graph with n nodes connected by (n-1) edges!

  • @waseemballoul5604
    @waseemballoul56042 жыл бұрын

    Finally I found the best channel That's amazing I wish to support you more ...

  • @Cassandra81552
    @Cassandra815523 жыл бұрын

    Brilliant. Nice explanation. Really helpful 👌👏👍

  • @JamesBrodski
    @JamesBrodski2 жыл бұрын

    Great video! Thank you so much for it.

  • @peterpete5214
    @peterpete5214 Жыл бұрын

    Thank you for the clear explanation very easy to follow. You got a new subscriber keep up the good content👍

  • @KodySimpson
    @KodySimpson2 жыл бұрын

    This is the best video ive ever seen in my life

  • @Aughadi
    @Aughadi Жыл бұрын

    Best Explained !!!!! Thanks from India 🇮🇳!!!!!

  • @nitinkulkarni7942
    @nitinkulkarni79423 жыл бұрын

    This is simply an amazing explanation

  • @oscareriksson9414
    @oscareriksson94142 жыл бұрын

    Really good explaination!

  • @makhdoom65
    @makhdoom65 Жыл бұрын

    Amazing explanation. My teacher did the same but you explained it way more easier.

  • @alessandroporfirio1910
    @alessandroporfirio19102 жыл бұрын

    Very good explanation, thank you!

  • @flamess007
    @flamess0072 жыл бұрын

    I really love how you explain and the music, I really love this yt channel thank you so much

  • @ishankhan3912
    @ishankhan3912Ай бұрын

    The best explanation!!This guy is a gem

  • @geges2395
    @geges23953 жыл бұрын

    slick video and great explanation

  • @migzleon4047
    @migzleon40472 жыл бұрын

    The king of the hill is here... can't wait to become a patreon this content is 🔥...

  • @bivashchakraborty6518
    @bivashchakraborty65182 жыл бұрын

    Thank you so much!!! Much love from India.

  • @mohamedmoumni8916
    @mohamedmoumni89162 жыл бұрын

    Thanks for great explanation.

  • @dreamArmy34
    @dreamArmy34 Жыл бұрын

    I love ur channel 🥺 such a wonderful explanation

  • @jenso413
    @jenso413 Жыл бұрын

    wow, what a great explanation! thank you!

  • @DEEPAKKUMAR-wk5pk
    @DEEPAKKUMAR-wk5pk2 жыл бұрын

    great explaining video for Graph Thnaks

  • @crunchy3501
    @crunchy35012 жыл бұрын

    You're the man! Perfect explanation!

  • @sahandsanaei555
    @sahandsanaei555 Жыл бұрын

    superb explanation!

  • @m.pashakhoshkebari2045
    @m.pashakhoshkebari20453 жыл бұрын

    So well done! Great job

  • @bhiep3185
    @bhiep31853 жыл бұрын

    Your channel is amazing! How you don't have hundreds of thousands of subscribers is beyond me. Please keep up the good work!

  • @Reducible

    @Reducible

    3 жыл бұрын

    Thank you! Hopefully we get there in the future :)

  • @sivsivsree

    @sivsivsree

    3 жыл бұрын

    @@Reducible you will

  • @TomBenBel
    @TomBenBel3 жыл бұрын

    Beautifully animated video, though forgive me if I don't like this way of introducing DFS. The main problem is that most of the applications could just as well be solved without DFS: Cycle Detection: DFS does not give you all cycles in the way you described, and just determining whether a graph contains cycles can be done by BFS or similar also. Finding Connected Components: Any Traversal technique will do nicely. Topological Sort: Take Kahn's algorithm. The idea there is your reasoning at 18:37, but translated more directly into an algorithm. Maze: There are several ways to create a maze, but granted this one is elegant :) This sometimes leaves students wondering whether DFS is just a bad alternative to BFS for the path finding problem. It is not! Of course some applications are harder to explain in a video, but here is a surprisingly useful application somewhat related to your examples: Partitioning a directed graph into strongly connected components (SCCs, Sets of nodes where you can reach every node from every other node). This is useful in e.g. model checking, where you want to proove the correctness of a program, which can be reduces to finding an SCC with a special marking and a loop. Checking whether an SCC has a loop and is marked is usually trivial (loop at least two nodes in the SCC or a reflective edge). Or you might want to replace SCCs with single nodes, yielding a DAG. This e.g. extends many planning algorithms to handle circular dependencies (exactly the SCCs with several nodes). Basic idea without any proofs: Every SCC is represented by the node within it first encountered during DFS. Start by assuming every node is its own SCC and start the DFS. If you keep a hashset of all the nodes currently on the stack (or mark nodes as on the stack), you can efficiently determine whether a node was encountered twice along a path. If that happens, you found a loop and can merge all SCCs on the stack from the first encounter to the second. An SCC is guaranteed to no longer grow once DFS leaves it (through the node representing it, which you can detect). At that point, note the SCC down. Side node: Like in your example, the SCCs outputted this way are topologically sorted. Sadly, most students never get to learn these more useful applications of DFS, but hey, thats why I'm writing long comments :) Thanks for reading!

  • @ron3799

    @ron3799

    2 жыл бұрын

    wait, this is really useful info. thank you for taking the time to write this all !

  • @Oscar-vs5yw
    @Oscar-vs5yw Жыл бұрын

    This seems like a very useful algorithm to know, I feel like I can already see some applications of it

  • @mahdivakili7353
    @mahdivakili73533 жыл бұрын

    Perfectly done. Thanks

  • @Yang2j7
    @Yang2j72 жыл бұрын

    Literally just learned about this in class today and it popped up in my recommendation. KZread algorithm is getting insane.

  • @vaibhavgaur261
    @vaibhavgaur261 Жыл бұрын

    good animation easy explanation covered a variety of algos in just 20 min. 👍👍👍

  • @Cruizzerr
    @Cruizzerr2 жыл бұрын

    great explanation, thanks.

  • @avinashmbhat4256
    @avinashmbhat425611 ай бұрын

    Really amazing video 🙌🙌

  • @__goyal__
    @__goyal__3 жыл бұрын

    Thanks a lot for the explanation!

  • @inishkohli273
    @inishkohli2736 ай бұрын

    I rarely comment on KZread but I must say you are the exact version of KZreadr and tutor I am dreaming to be..Before reading the solution and algorithm, we must understand why it was created , what was the intuition behind it... and second thing I loved is bg music..

  • @kasyapdharanikota8570
    @kasyapdharanikota85703 жыл бұрын

    please continue making these kind of videos . .....!!!!!!

  • @AlessandroBottoni
    @AlessandroBottoni3 жыл бұрын

    Fantastic video! Kudos!

  • @hrithikkale443
    @hrithikkale4433 жыл бұрын

    thnx for this amazing animated visulization.

  • @davidkulman2291
    @davidkulman22916 ай бұрын

    Incredible video!

  • @mahyarekramian9040
    @mahyarekramian90403 жыл бұрын

    very best tutorial , well-done

  • @koberowland9798
    @koberowland97982 жыл бұрын

    Awesome video you are a amazing teacher

  • @user-wc1sm8cj8s
    @user-wc1sm8cj8s3 жыл бұрын

    *Great Content!!!* Understood a lot

  • @068_gauravchakraborty
    @068_gauravchakraborty2 жыл бұрын

    very nicely explained thx a lot

  • @IndieDeveloperGuy
    @IndieDeveloperGuy2 жыл бұрын

    Thank u very much , the video helped a lot ❤️

  • @milind-9683
    @milind-9683 Жыл бұрын

    Awesome as always!

  • @1matan5
    @1matan53 күн бұрын

    greatly explanied!

  • @nirmalparmar9655
    @nirmalparmar96559 ай бұрын

    Great explanation, it would be awesome if you can create similar videos around Trees (diff trees and usages).