Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms
ฝัง
- เผยแพร่เมื่อ 19 ธ.ค. 2018
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
DFS and BFS are not just graph search algorithms. They are a fundamental method for searching relationships in a certain way and visiting nodes of any sort in a desired order.
These relationships may be represented in a graph, or we may be checking the distance one string is in character changes from another string, OR we may be traversing a tree a certain way.
These are searching concepts, not just graph concepts.
Implementation
DFS can be done iteratively using a stack or done recursively because the call stack will serve as the stack to remember points to backtrack to.
A stack structure can replace our stack frames from recursion, this is why DFS can be written recursively, due to the Last-In-First-Out (LIFO) of the order nodes are processed.
BFS is done iteratively. It uses a queue that has a First-In-First-Out processing order.
Use Cases
DFS is good for things like backtracking, getting to leaf nodes in a tree, or anything where we want to prioritize going very deep into a path and exhausting possibilities before coming back.
BFS is better for things like finding if a path exists between one node to another since it prioritizes width of search over depth (hence "breadth-first") and finding distance or "levels" something is away from something else.
The Method
1.) Choose the data structure based on the search.
2.) Add the start node.
3.) Remove the a node from the data structure.
4.) If the node has not been seen
4a.) Mark it as seen in the "seen" set.
4b.) Do work on the node.
5.) For each of the children
5a.) If child has not been seen (not bee processed)
5ai.) Add the child to the data structure.
Repeat while the data structure is not empty.
Time Complexities
If relationships are represented with an adjacency list then:
Time: O(V + E)
Space: O(V)*
Where V is the total number of vertices (or nodes) visited and E is the total numbers of edges traversed.
*Although things will vary. We only care about the MAXIMUM amount of nodes in the data structure at one time. If we are doing DFS on balanced tree the space complexity would be O(h) where h is the height of the tree since we would only have a path h nodes long at MAX living on the stack. Same for if we do a level order traversal of a tree. The space will only be the MAXIMUM WIDTH of the tree because we would only keep that many nodes on the queue at MAX at one time. And on and on...just depends, ask your interviewer whether they want worst, average, or best case analysis.
"adjacency list" means each node stores its adjacent neighbors in a list
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - วิทยาศาสตร์และเทคโนโลยี
Table of Contents: (and side notes)
Finding A Room 0:00 - 0:21
DFS & BFS Introduction 0:21 - 3:37
DFS & BFS Algorithm Outline 3:37 - 6:07
Depth First Search Example 6:07 - 10:16
Breadth First Search Example 10:16 - 14:00
The Pattern Of Breadth First Search 14:00 - 14:32
Wrap Up 14:32 - 15:02
Depth first and breadth first search on a graph. These are just approaches to searching and are raw by themselves. Graph search in "real life" makes use of certain heuristics along the way to get to the answer faster (whatever the problem may be).
Also is this is DFS or BFS on a tree where a cycle is not possible then the hashset is not necessary.
Dope thanks man
ye
You deserve an Academy Award for all these videos you have made.
hahahahahaha
He did absolutely nothing . U were too lazy to understand it on ur own .
@@mujtabaarfat717 😐
@@mujtabaarfat717 damn bro who hurt u
DEADASS! Your content is so helpful and it just encourages me to see a person of color with so much passion. Thank you for these videos!
This guy can explain rocket science to a baby, in-depth knowledge with crystal clarity
I remembered this video from the last time I needed to prepare for coding interviews, and now that it's that time again I came right back. I appreciate the simple, yet thorough explanation!
This channel is surely one of my favourite on programming.The way he explains is breathtaking.He is breathtaking.😊
ur my favorite
You are breathtaking! You are all breathtaking!
@@anarbay24 Wake the f*ck up samurai! We have a city to burn!
After watching this video, DFS and BFS finally clicked for me. I have watched countless videos on the subject, but you are the only one that explained it simply enough for me to understand. Thank you so much! Just subscribed.
Out of all the videos I watch on these topics you make it seem very clear.
Now you gave me confidence to finally solve this stuff.
Thanks!
I just loved the explanation. My fundamentals for DFS and BFS were never this much clear. Thanks for doing all good work. Keep it up and keep posting more videos like this
i really love the way you explain things. you always sound excited while explaining and that motivates me to learn and keep my attention on what you're saying. awesome content, sir! 🔥
Why can't I have this much energy and clarity at 7am??? Great explanations. Thank u.
lol I was a rabid lion back in the day with no mic equipment
Great job done, after your explanation I finally understand everything. Keep on doing good work!
That is the goal. Keep flourishing.
Mate! I really appreciate you for all these videos! I always come to this channel first and watch a video when I got any data structure related problems huge fan!!
Man you are awesome. Love the energy more than anything. You could find a hundred videos on DFS and BFS but you cant find the energy. Cheers.
Can't wait to see your other videos on BFS & DFS and practically how they are leveraged. I really "get you" and your way of explaining. Thank you!!
nice ha, if you like this join our class, I'm posting videos there as "the new TH-cam" channel
This is one of the most intuitive explanations of DFS/BFS!!
Hey, this explanation is freaking baller. I've been working as a SWE for a couple years but forgot a few of the basics. Switching jobs right now and while I study this has been clutch. Still struggling to get DFS recursively. But the stack way is foolproof right now!
Thanks dude!
You are extremely good at explaining things! Most of the DFS&BFS tutorial video on TH-cam is just to go through the code and example but you mentioned when and why we use DFS or BFS from a high-level perspective which is good for beginners to understand those algorithms.
thx
Got an interview next week. Just what I needed! Good stuff, guys
it is just Ben now (this is Ben) and good luck!
You are so good and enthusiastic at explaining, I never get bored learning something from you. Real good!
thanks
You explain very well. You helped me with another concept last year, I was so happy to see your face in the search results for DFS and BFS algorithms because I have dry slides. I have hope for passing my AI class now haha.
Got a google internship interview coming up, hope these vids help. You're a legend man
ok - let us know if u get ti
practising on cf will help more
@@BackToBackSWE Just passed the Hiring Committee! Thanks for your help!
@@AH-xb7eb nice! I’m having mine next week. What type of questions were you asked during the interview?
@@MundoTecChannel I was asked a graph problem, which is funny because this video goes over graph traversal. It was a leetcode medium type of question. I was also asked to create a class responsible for managing items, with several follow ups.
You just helped me write a 7 page document on depth first search and how it applies to a maze, I cannot thank you enough.
you have a real gift for CS and for teaching, my man
Brilliant explanation! Thanks for your energetic effort, I love it.
Great explanation! It's such a relief to finally find a video of someone I can actually understand.
nice
your channel is really helping me with my university data structures course!
This channel is so underrated! Thanks so much for this!
thx.
Wow! All my doubts are now gone after seeing this video... Thank you so much brother
great - sure
I’m about to graduate and with most jobs requiring a technical of some sort I finally decided to start grinding LC. The impostor syndrome feels so real but your videos are so insanely helpful I’m regaining my confidence. All I can say is thank you. It’s rare for people to be able to explain things so well it feels like.
This is the best video on the topic I’ve ever seen, thank you so much for this!
Thank you
For some reason, this concept was so hard for me to understand, but you explained it so well. I'm a visual learner and I think I finally get it, so thank you!
Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/
Not all heros wear cape. This guy is JUST AMAZING.. He is a REAL HERO..!!
Word out there needs to know about this guy.
Thanks for taking your time to do this.Really appreciate it.
sure
This is some fantastic instruction, my friend. I look forward to more.
ye
appreciate the content man , its pretty clear explanation, keep it up !
This is fantastic -- thank you for making a technical, educational video that's actually enjoyable to watch
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Thanks a lot for the very clear explanation. Keep up the great work.
Just what I was looking for! Clear and concise!!
nice.
Yo, you explained so clearly. Thank you!
Awesome videos man! I'm currently taking a Computer Science course with Lambda School and they have been teaching us all these Data Structure techniques that are pretty common in a workplace. From what I understand I have yet to work in a real world environment, I mean I've done some contract work being a Team Lead and managing a team but now I have to actually think like an engineer and I got to say your videos have been super helpful! Thank you for your free content and work you've put together. I really love this Profession field.
Great. Lambda school, nice! Keep going! The internet is here for you. Do you know anyone at Lambda school we could talk to? It'd be cool to do a deal with them as we grow.
Thank you SO MUCH! Your explanation of Depth First Search with a stack finally helped me understand it. Thank you so much!!
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Alright, it is 7 in the morning today we are doing a breakfast search! I was looking forward to a drive to the Ihop and enjoying some vicarious breakfast!
Iam knowing the real problem I had in DFS , but now I knew it perfectly .. amazing 👍🏿
Thanks for the great tips provided! Helped me a lot :)
The best explanation ever! Thank you so much!
sure
THANK YOU! Great channel you got there! Keep up the good work
ok thanks
Great video. Thanks! One BFS issue, though: The place to mark a node is seen/visited should be before it is enqueued, instead of after it is dequeued. This makes a difference, for example, when you need to trace back the shortest path via parent nodes.
you are way better than my professor explaining this at uni, thanks mate !
Beautiful explanation, cleared all my doubts,. Thanks man
nice and sure
this helped me out tremendously. Thanks for the clear explanation!!
Glad it helped 😄 We'd love for you to check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Great! Clearly explain everything. Thank you !
Great explanations, so easy to implement after seing this.
Thanks a lot from France !
sure!
Thank you for easily and effectively explaining this topic in a concise manner!
Happy Holidays! Really glad to help 🎉 Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Did I understand BFS and DFS in 15min?....Hellll yes 🔥🔥
The video is great! Your explanation is very clear and helpful! Can you also post a video of how to DFS on a string?
I have a video for that. Decomposition of an IP address. And it is not really depth-first search. Wikipedia: "Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures."
Love your videos. Super useful and really articulate, thanks!
sure
One minute in , I clicked the subscribe button!
Thanks man!!
nice
wow thank you! You explained the concepts so well and clearly!
hey
on BFS you left "H" when you were mentioning the children of D now it is changed the processing order
and Thank you for the awesome video you're the best I know keep it up
Nice Explanation as always!
thx
Great explanation, this was very clear ! thanks for the help
Happy to help
Hey I'm only 2 minutes in but god damn this is really well explained. I loved the visualization and the when to use each. Thank you! I'm a self taught developer so this content is just what I needed to help me solve a problem.
sure and great
Thank you for making this video!
Sure
By far the best explanation! Thanks
sure
Minor mistakes but well-explained and really enthusiastic! :)
Incredible explanation. Very passionate 👍. Needed a refresher on this before Amazon interview.
nice
@@BackToBackSWE Failed cause they asked me binary search 😂😂
thank you so much ; you're the man .
Simple and easy to understand , Thank you very much
sure
This video is truly a blessing
yes
You are an excellent teacher, thank you
sure
thanks for the clear explanation
it was very helpful :)
Thanks! why dont you try our 5 day free mini course backtobackswe.com/
Legend man! thanks!
youre actually such a good teacher man
thanks
Explained in a very simple manner.
thx
Amazing explanation :)
Thank you so much you teach really well!
Glad it was helpful!
Best explanation ever!
Very helpful!Thank you very much!!
sure, thanks for watching
Thank you a lot Dude for helping backbenchers like me. :)
ur gud
You're videos are really helpful
Thanks
you just saved my degree man :') bless
This is awesome! I still have trouble determining when I should use either BFS or DFS in a problem. Any tips on how you can be like "oh BFS or DFS can be used here"? This makes sense with nodes but how about when you're working with strings/2d arrays/etc.?
You are a talented teacher!
thanks
Goes deep and comes back out!
ok
Amazing explanation!
thx
Love your videos !. Hey can you please do a video on Course Schedule - Leetcode problem 207
I'm aware of that problem. But to be fair to patrons of this project I only take suggestions from those who support the project on Patreon. I didn't do this before the Patreon launched but now I have to be fair to them.
Damn Such A beautiful explanation. Thankyou. Love from INDIA.
really helpful man!!
thanks, glad it helped
14:59 that is what she said!
great video, thanks a bunch!!
Nice channel bro, subbed!
yoyo
Great stuff. Thanks!
sure
Thank you, sir, you are extremely good at explaining! Are there other algorithms that I could use to find a set of feasible paths between two nodes in a graph? I'm not searching for all possible paths but i m looking for a set of most promessing path
If I need some explanation . I look for your videos man. That's the end point for me, I just get what I need.
great.
Glad to see another brotha doing this. Wish we had more of us in tech
hey
Give this man a Golden Teacher medal
Great Explanation, will you be able to do a video on Topological Sort, please
thanks and we have that on backtobackswe.com (paywall)
We use stack when it goes deep. Imagine like in a real scenario where you would want to hold items. If there was a hole you would not be able to hold items vertically, hence you would use stack as it is like a deep hole with its ends closed. But queue is open on both ends and would only hold items when parallel. Hence its broad and can be used during BFS. Just for a quick mapping in head.
nice
Man u r underrated. U deserve more subs
Nah I'm just normal and we will do fine
In the DFS code, if a vertex has been seen and is being popped again, its adjacent vertices must have been seen already. So if that if condition in the middle doesn't hold (i.e. if seen contains current vertex), you should continue the loop right away.
great stuff man
thanks