Depth First Search Algorithm | Graph Theory

Depth First Search (DFS) algorithm explanation

Source code:

Video Slides:

0:00 Depth first search as an algorithm template
1:04 Simple DFS example
3:30 Depth first search pseudocode
5:10 Finding connected components with a DFS
7:32 connected components source code
9:27 What else is a DFS useful for?

===================================

Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on YouTube:

[nmamano]

4:55 It is pretty clear, but if anyone is wondering, "graph[at]" shuld be "g[at]" in the DFS pseudo-code. Great video!

[anhmai]

this is way better than a 2-hour lecture from a CS professor with multiple PhD's explanation. Thank God I found your video.

[J]

The best explanation a developer could ever ask for. You have cut out all the possible crap and got to the point.

[iyadelwy]

An explanation with the help of a good example > A CS professor with 2 PHD's explaining it in sheer theory

[karthikrangaraju]

So basically Google's notorious "Number of islands" problem is basic graph theory == Finding connected components using DFS! Thank you William

[wanqingli]

this visualization is so clear and william is so good at explaining omg, thx for saving my algo exam

[miriyalajeevankumar]

You are the best in the entire youtube for Algo and DS!

[VarunVishwakarma]

I was scared of graph and you made it so easy.Thanks a lot.

[luisfelipe]

That's such a great video! I loved the minimalist visual and explanation!

[colegartner]

Thank god for this man, the best explanation with visuals a comp sci major could ask for.

[gokulkurup]

great video. jutst a gotacha for future learners, the dfs findComponents algo only works well for undirected graphs and will give weird results with directed graphs.
ex. in directed graphs if you take the picture 7:25 the for loop first sees node#2. however there is no path from 2 to 3 even tho they are in the same component. so instead of the answer which is 5 you get 6

Excellent video tho and thanks for the explanation

[isaacnewman]

I understand the visual example for DFS, but I struggle with understanding the pseudo code. However, this is a great video!

[TechItEasy]

These videos are awesome so far... will watch them through, undoubtedly multiple times!

[MrDayTwo]

Waaaay better than leetcode explanation. Thanx!

[rodituclashroyale]

You can reverse the order of calling the neighbours in this implementation, so the output will the same as You would use stack dfs algorithm - the one that uses stack instead of recursion. Because if You add neighbours to the stack the last one will be called first since it will be popped first.

[roman_mf]

So happy I found your channel. Thanks for your efforts and quality content. Short, to the point, and the animation done just right. :-)

[yagzgazibaba]

If the graph is cyclic one then inside dfs method you also need to check if current node visited or not

[IagoSB__.]

Thank you sir, your explanations are always very clean and simple

[sandeepkryadav]

Thank you very much for such an amazing video series, the content of the video is so organized that whenever I think of some scenario that scenarios explanation comes to next. Amazing :)

[vigneshsr]

bought the course, thanks for all the help.