DFS/BFS Analysis - Graph Theory 06

ERRATA (Expand to read): At 8:50, the expression shown after "Complete Graph" should have been E = V × (V-1). Thanks to Arun Satyarth for pointing out the error!

Now that we know how Depth-First Search and Breadth-First Search works, we can now study them both further! In this episode, we look at the following:

1) Recursive formulation of Depth-First Search
2) How to implement Spanning Trees
3) Time complexity of BFS and DFS

= Credit =

= 0612 TV =
0612 TV is your one stop for general geekery! Learn about a variety of technology-related subjects, including Photography, General Computing, Audio/Video Production and Image Manipulation! Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!

-----

Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.

[NERDfirst]

ERRATA: At 8:50, the expression shown after "Complete Graph" should have been E = V × (V-1). Thanks to Arun Satyarth for pointing out the error!

[DongningWang]

I like your explanation of time complexity!

[arunsatyarth]

Thanks for this video. Great work. I wanted to point out one thing though which has caused some confusion in the rime complexity.
Here, E is number of edge in the graph. Not the number of edge for a single vertex. So at 8:50 what you mentioned "E=V-1" is wrong. Here you gave a different meaning to E as number of edge in a vertex.

[jordansquires]

These videos are amazing! Thanks a lot!

[BrijeshYadav-vlbj]

@0612 TV w/ NERDfirst . Not able to locate your Graph Theory playlist. Can you please share.

[shreyakhatal]

why dont we multiply lvl*lEl as there is an inner loop. why do we add