Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms
Вставка
- Опубліковано 9 лют 2025
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 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!
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!
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
5 years later this man is still the goat
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.
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!
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 are extremely good at explaining things! Most of the DFS&BFS tutorial video on UA-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
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/
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.
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.
Great job done, after your explanation I finally understand everything. Keep on doing good work!
That is the goal. Keep flourishing.
You are so good and enthusiastic at explaining, I never get bored learning something from you. Real good!
thanks
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.
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 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! 🔥
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.
Not all heros wear cape. This guy is JUST AMAZING.. He is a REAL HERO..!!
Word out there needs to know about this guy.
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
This is one of the most intuitive explanations of DFS/BFS!!
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
Not sure where you went. But I am back here to tell you, I watched a lot of your videos. and I did end up working for Amazon as SDE for almost 4 years.
Thank you.
Hope you doing well.
Great explanation! It's such a relief to finally find a video of someone I can actually understand.
nice
pulled it, processed it, add its children.
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.
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 UA-cam" channel
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
Incredible explanation. Very passionate 👍. Needed a refresher on this before Amazon interview.
nice
@@BackToBackSWE Failed cause they asked me binary search 😂😂
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!
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!!
This is the best video on the topic I’ve ever seen, thank you so much for this!
Thank you
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
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 😀
Got an interview next week. Just what I needed! Good stuff, guys
it is just Ben now (this is Ben) and good luck!
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/ 🎉
Iam knowing the real problem I had in DFS , but now I knew it perfectly .. amazing 👍🏿
My appreciation for people who make free videos is even greater now that university is closed because of the virus
hello
you have a real gift for CS and for teaching, my man
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.
your channel is really helping me with my university data structures course!
Did I understand BFS and DFS in 15min?....Hellll yes 🔥🔥
you are way better than my professor explaining this at uni, thanks mate !
One minute in , I clicked the subscribe button!
Thanks man!!
nice
Brilliant explanation! Thanks for your energetic effort, I love it.
CORRECTION??: I believe the DFS has an error on the whiteboard at the end where it says stack.push(adjacent) which is incorrect as Stack stack means that it needs to push only an integer value, so the correct code would be stack.push(adjacent.id); Unless the Stack should be a node instead, so Stack stack = new Stack()...
Other than that, this is a perfect explanation! Thank you.
Maybe? Dont remember old video and no one watched then and tahnks
youre actually such a good teacher man
thanks
I love Abdul too but I have to say B2B is better in this video. Explains very clearly and thoroughly. Good job, man.
thanks.
Can you please explain how curr.adjacents work inside enhanced for loop? time stamp
5:55
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.
Thanks for taking your time to do this.Really appreciate it.
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/
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
Beautiful explanation, cleared all my doubts,. Thanks man
nice and sure
Give this man a Golden Teacher medal
This is some fantastic instruction, my friend. I look forward to more.
ye
Explained in a very simple manner.
thx
Minor mistakes but well-explained and really enthusiastic! :)
By far the best explanation! Thanks
sure
Great explanations, so easy to implement after seing this.
Thanks a lot from France !
sure!
You are a talented teacher!
thanks
this man is the new organic chemistry tutor. except it’s for computer scientists
14:59 that is what she said!
great video, thanks a bunch!!
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/ 🎉
This video is truly a blessing
yes
So we can basically use any kind of data structure for what nodes to process next. Stack for DFS, Queue for BFS, HashSet for random. I think in some cases HashSet would be more useful.
ye
@@BackToBackSWE There is only one problem. If you use DFS iteratively to try and find cycle in a directed graph, you might run into lot's of implementation problems as you need to backtrack the remaining nodes and it;s quite hard to do it iterative.
thanks for the clear explanation
it was very helpful :)
Thanks! why dont you try our 5 day free mini course backtobackswe.com/
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.
Just what I was looking for! Clear and concise!!
nice.
Glad to see another brotha doing this. Wish we had more of us in tech
hey
Thanks a lot for the very clear explanation. Keep up the great work.
Damn Such A beautiful explanation. Thankyou. Love from INDIA.
Love the Academy acceptance speech. Great job remembering to thank your parents!
what did I do? This is a really old video so I don't remember
@@BackToBackSWE gave an academy award speech of sorts right at the start of the video
Great! Clearly explain everything. Thank you !
Amazing and concise explanation
you are my savior
great
THANK YOU! Great channel you got there! Keep up the good work
ok thanks
Goes deep and comes back out!
ok
You're videos are really helpful
Thanks
Yo, you explained so clearly. Thank you!
Great stuff. Thanks!
sure
Thank you a lot Dude for helping backbenchers like me. :)
ur gud
Great explanation, this was very clear ! thanks for the help
Happy to help
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
Great explanation. I think it is better to introduce BFS and DFS in the context of graphs before they are introduced in the context of trees. (At least that is better for me). I would like a bit more of an explanation about the time and space complexities of these different algorithms.
Thanks, ok, and I cannot do that because replying fast to comments but I would if I could
appreciate the content man , its pretty clear explanation, keep it up !
Simple and easy to understand , Thank you very much
sure
You are very dedicated. Really cool!! Thanx
Amazing explanation!
thx
wow thank you! You explained the concepts so well and clearly!
This channel rocks... those explanations are crystal clear, this channel will grow in the order of O(n!) :-)
haha k
@@BackToBackSWE I SAY O(2^N) !!!!!
@@DishaSaraiya_xo ok lol
Thank you very much for the video. I just found one small correction to be made at about 3:19 in the video where you say BFS' priority is to go deep. I think it should have been for DFS.
yeah, if I said that ur right
Nice Explanation as always!
thx
Best explanation ever!
In your example -> Stack object should be typed for Node and not for Integer. But anyway, thank you, very clear explanation!
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
Man u r underrated. U deserve more subs
Nah I'm just normal and we will do fine