Why is DFS and BFS so confusing?
Posted by FlashyFail2776@reddit | learnprogramming | View on Reddit | 11 comments
Just started my DSA class at university and I gotta say this DFS thing is not easy at all. I understand the logic but the implementation is something else. The leetcode problem 39 in particular has me so lost. Anyone have advice to get better when you’re starting out with this? (I understand recursion and what not but DFS is tricky)
IncognitoErgoCvm@reddit
I think your hubris might be getting in the way here. You definitely don't understand the logic if the implementation is unclear to you.
FlashyFail2776@reddit (OP)
Mhmm you might be right. Looks like i’m gonna be reviewing it again
Mysterious_Screen116@reddit
Because you haven't spent enough time thinking about it.
troy-boltons-dad@reddit
I highly recommended practicing with the exercises on this page, they helped me a lot https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/GraphTraversal.html
peterlinddk@reddit
Try to build a visual maze solver - use whatever visualization tool you prefer: processing, p5.js or pygame are good choices for java, javascript, or python respectively.
Build the solving algorithm using DFS - preferably with a stack datastructure rather than with recursion - and see if you can get it to visualize in steps how it visits the different cells, and when it backtracks, that'll really help your understanding.
Here's one I built to demonstrate the visualization: https://petlatkea.github.io/dsa-games/stack/index.html don't look to closely at the code :) It isn't particularly well-structured ...
Then modify the maze so that it has more than one solution - and create another visualization using BFS - now with a queue datastructure, and watch as it finds the shortest route.
-
another nice demonstration of both is the Flood Fill algorithm - https://en.wikipedia.org/wiki/Flood_fill - that can either be DFS (using a stack) or BFS (using a queue), but achieving the same result. Don't just look at demonstrations, write visualisation code yourself!
NotRexGrossman@reddit
The best thing you can do is go to your professor’s office hours and speak to them about it.
Another decent option would be to find a visualization tool. These are all just a quick google search away.
FlashyFail2776@reddit (OP)
got a meeting with a TA in 2 hours. Thanks
Beregolas@reddit
So, I was a tutor for DSA at university, it is completely normal to be confused. It takes most people a while to get a hang of it, but it will get easier once you already have an understanding of a few algorithms and data structures.
So, first: The Algorithms can both be written either in iterative or in recursive form. Some people find one more intuitive, some the other. If you're having problems with a particular formulation, try switching to the other version. They can easily be found online.
Secondly: Go for visualization and execution. Write the Algorithm down on a piece of paper with a pencil, and write a few graphs next to it. Then execute the algorithm by hand and see if you can figure out how/why it works. Once you can predict the next few steps from pure intuition, without thinking about it, you should have gotten it.
Third, and the easiest: There are excellent visualizations for both algorithms out there. Maybe watching one while going over the pseudocode or implementation of the matching algorithm to see what the code does helps. This site has a lot of good visuaizations: https://www.cs.usfca.edu/\~galles/visualization/DFS.html
And lastly: Go to the office hours. That's what your university is for, and if you have tutors / professors that at all care, they will gladly sit down and explain it to you. Going over this on a whiteboard is normally the best and most effective way to learn / teach.
FlashyFail2776@reddit (OP)
Thank you so much for this detailed response!!! Yeah I have a meeting with a TA in about 2 hours so hopefully he manages to clear it up 😭
Celodurismo@reddit
Well you don't need recursion, solve it without first
AutoModerator@reddit
To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.