Depth First Search Algorithm

This is one of the important Graph traversal technique. DFS is based on stack data structure.

Analysis:

The time complexity of DFS using Adjacency list is O(V + E) where V & E are the vertices and edges of the graph respectively.

[danielxu]

this 4 minute video explains better than my prof did in 1 hour

[csandreas]

So the differences between depth first search and breadth first traversal are:

a)Breadth traversal has a queue but depth search has a stack
b) The other difference you will notice with node C at 2:13. In breadth traversal the result would be C D E F, in depth it is C D E H.
other difference at 1:30 where in depth the result is S C D but in breadth it is S C G

[NamithaLIAF]

I learnt DFS in less than three minutes, compared to 40 hours of a semester -_- Thank you so much, this made DFS so easy! :)

[vishnuvishnu]

At the peak times to attend the exam it is very useful 😛😀😀😀

[PuthyMol]

Thank you very much for your video. Abut 4 minutes of your explaining is more effective than my teacher explain 1 hours 

[chendongyuan]

Best DFS animation ever watched. Thank you man!

[foolishmusic]

Difference between depth first search & breadth first search:

BFS looks at each adjacent node and doesn't consider the children of those adjacent nodes.
DFS looks at each adjacent node, and looks at all the children of the current adjacent nodes. It again, looks at the children of the next adjacent node (adjacent to the children of the prevoius).

[Akashpagol]

I had trouble understanding the pseudo code given in class... your explanation is precise and to the point. I find it very easy to relate it to my pseudo code. Thank you very much!

[Bartekdex]

Awesome videos. Simple explanation. This was exactly what I needed. Sometimes it's just nice to see how an algorithm works than to see the code only and struggle to guess what's going on in it.

[anhtuannguyen]

this is a simple search strategy, but i have trouble handling with some misunderstanding about the stack. your video had solved it nice and tidy. i have no confusion now. thanks a lot.

[sriramOV]

This is one of the best video for DFS in the whole internet <3

[saravanansubbiah]

this short video conveys the message very effectively..nice work

[coreyownz]

Was a whole lot easier coding it from your example than reading pseudo code, thanks a bunch, great videos

[malharjajoo]

You have forgotten to mention the most imp point -

1) This is iterative version of DFS ( there is a recursive version too )

2) This DFS will only give you all connected components within the same SCC.
Anythign disconnected is not seen

[gogateiit]

That was truly an appreciation to our hard work. Thanks Namitha.
If you like the video, do subscribe for more such video. You can explore other videos too. I hope you'd like those too. Do share it across your friends.

[mihirmalladi]

Hi. I have a question how can we look for cycles in the graph from this approach? Please let me know.

[michaelchung]

If the ADT, Stack, is used, the implementation is non-recursive (iterative). If the code refers to the pseudocode of non-recursive DFS in Wikipedia and the neighbors are pushed onto the stack in alphabetical order, then the output sequence should be ASGHEFCDB; moreover, A should be popped immediately after it is pushed onto the stack.

[FranciscoCostaRamos]

Hey, again, can you add the discovery (d) and finalization (f) times? thanks

[muralikrishnaraju]

Thanks a lot for this wonderful explanation.. DFS can't be explained any better than this..

[tubex]

Very clear and easy to understand the concept of dfs - pls make more vids