Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms

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

[@BackToBackSWE]

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.

[@timgoppelsroeder121]

Dope thanks man

[@BackToBackSWE]

ye

[@taiwan.1]

You deserve an Academy Award for all these videos you have made.

[@BackToBackSWE]

hahahahahaha

[@mujtabaarfat717]

He did absolutely nothing . U were too lazy to understand it on ur own .

[@yutaitadori7318]

@@mujtabaarfat717 😐

[@ashwinpande7095]

@@mujtabaarfat717 damn bro who hurt u

[@tachylamurray9452]

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!

[@pranitachikorde603]

This guy can explain rocket science to a baby, in-depth knowledge with crystal clarity

[@reedmurphy3073]

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!

[@AdityaMishra-ve6yu]

This channel is surely one of my favourite on programming.The way he explains is breathtaking.He is breathtaking.😊

[@BackToBackSWE]

ur my favorite

[@anarbay24]

You are breathtaking! You are all breathtaking!

[@jfklittle]

@@anarbay24 Wake the f*ck up samurai! We have a city to burn!

[@mouseclicker4955]

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.

[@Labattfartoui]

Why can't I have this much energy and clarity at 7am??? Great explanations. Thank u.

[@BackToBackSWE]

lol I was a rabid lion back in the day with no mic equipment

[@milanpatel6240]

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

[@joy-sm5sl]

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! 🔥

[@_janol]

Great job done, after your explanation I finally understand everything. Keep on doing good work!

[@BackToBackSWE]

That is the goal. Keep flourishing.

[@alanwang6563]

You are extremely good at explaining things! Most of the DFS&BFS tutorial video on KZbin 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.

[@BackToBackSWE]

thx

[@chrisbaca3997]

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!

[@metehanemir7454]

You are so good and enthusiastic at explaining, I never get bored learning something from you. Real good!

[@BackToBackSWE]

thanks

[@AH-xb7eb]

Got a google internship interview coming up, hope these vids help. You're a legend man

[@BackToBackSWE]

ok - let us know if u get ti

[@II_xD_II]

practising on cf will help more

[@AH-xb7eb]

@@BackToBackSWE Just passed the Hiring Committee! Thanks for your help!

[@MundoTecChannel]

@@AH-xb7eb nice! I’m having mine next week. What type of questions were you asked during the interview?

[@AH-xb7eb]

@@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.

[@nicholascastro4175]

Got an interview next week. Just what I needed! Good stuff, guys

[@BackToBackSWE]

it is just Ben now (this is Ben) and good luck!

[@wanyi8761]

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!!

[@metarun]

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.

[@cambeeler6374]

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!!

[@BackToBackSWE]

nice ha, if you like this join our class, I'm posting videos there as "the new KZbin" channel

[@DowryGoat]

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!

[@adamlee5620]

This is one of the most intuitive explanations of DFS/BFS!!

[@Canonall]

This channel is so underrated! Thanks so much for this!

[@BackToBackSWE]

thx.

[@DanielDiaz-rq3ko]

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.

[@andrews2945]

Great explanation! It's such a relief to finally find a video of someone I can actually understand.

[@BackToBackSWE]

nice

[@abdulmalikquadri7604]

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.

[@Anna-cl4rj]

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.

[@PorterRockwellsMyGrandpa]

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!

[@BackToBackSWE]

Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/

[@AvivaScott]

This is fantastic -- thank you for making a technical, educational video that's actually enjoyable to watch

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@CuriousWithOscar]

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.

[@BackToBackSWE]

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.

[@AaronMOliver]

This is the best video on the topic I’ve ever seen, thank you so much for this!

[@BackToBackSWE]

Thank you

[@DaggerMan11]

you have a real gift for CS and for teaching, my man

[@shivarammuthukumaraswamy7164]

Thanks for taking your time to do this.Really appreciate it.

[@BackToBackSWE]

sure

[@hoangvietng7100]

Brilliant explanation! Thanks for your energetic effort, I love it.

[@mallikarjunpidaparthi]

Wow! All my doubts are now gone after seeing this video... Thank you so much brother

[@BackToBackSWE]

great - sure

[@johndubchak]

This is some fantastic instruction, my friend. I look forward to more.

[@BackToBackSWE]

ye

[@nikoinfanto729]

Just what I was looking for! Clear and concise!!

[@BackToBackSWE]

nice.

[@historian2]

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!

[@RajSehmi5293]

Not all heros wear cape. This guy is JUST AMAZING.. He is a REAL HERO..!! Word out there needs to know about this guy.

[@kellybmackenzie]

Thank you SO MUCH! Your explanation of Depth First Search with a stack finally helped me understand it. Thank you so much!!

[@BackToBackSWE]

Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@etimezz]

your channel is really helping me with my university data structures course!

[@sercan272727]

appreciate the content man , its pretty clear explanation, keep it up !

[@sidagarwal43]

Beautiful explanation, cleared all my doubts,. Thanks man

[@BackToBackSWE]

nice and sure

[@sudeepwegapitiya2157]

Great! Clearly explain everything. Thank you !

[@mr_lamintun]

Thanks a lot for the very clear explanation. Keep up the great work.

[@DavidEspinosa21]

Love your videos. Super useful and really articulate, thanks!

[@BackToBackSWE]

sure

[@gabrielabezerra3434]

THANK YOU! Great channel you got there! Keep up the good work

[@BackToBackSWE]

ok thanks

[@shreeshsrivastava3614]

Yo, you explained so clearly. Thank you!

[@andrewsistek7600]

this helped me out tremendously. Thanks for the clear explanation!!

[@BackToBackSWE]

Glad it helped 😄 We'd love for you to check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@iliatadzhibaev3573]

The best explanation ever! Thank you so much!

[@BackToBackSWE]

sure

[@qingtianwang3511]

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.

[@amiraghdam]

Thanks for the great tips provided! Helped me a lot :)

[@benoitpoux6241]

Great explanations, so easy to implement after seing this. Thanks a lot from France !

[@BackToBackSWE]

sure!

[@yuezhang604]

The video is great! Your explanation is very clear and helpful! Can you also post a video of how to DFS on a string?

[@BackToBackSWE]

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."

[@johnnymeza5454]

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.

[@BackToBackSWE]

sure and great

[@MoSweiti666]

One minute in , I clicked the subscribe button! Thanks man!!

[@BackToBackSWE]

nice

[@mardokaymosazghi1296]

Nice Explanation as always!

[@BackToBackSWE]

thx

[@lciduhtak4278]

Iam knowing the real problem I had in DFS , but now I knew it perfectly .. amazing 👍🏿

[@shishirpai380]

Thank you for easily and effectively explaining this topic in a concise manner!

[@BackToBackSWE]

Happy Holidays! Really glad to help 🎉 Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/

[@nofaldiatmam8905]

you are way better than my professor explaining this at uni, thanks mate !

[@alex-pictures]

Great explanation, this was very clear ! thanks for the help

[@BackToBackSWE]

Happy to help

[@shilpag08]

By far the best explanation! Thanks

[@BackToBackSWE]

sure

[@FitCoder]

Explained in a very simple manner.

[@BackToBackSWE]

thx

[@khaledrefai8120]

Simple and easy to understand , Thank you very much

[@BackToBackSWE]

sure

[@sravanchittupalli9364]

Did I understand BFS and DFS in 15min?....Hellll yes 🔥🔥

[@kunalgulati6994]

This video is truly a blessing

[@BackToBackSWE]

yes

[@easifier]

thanks for the clear explanation it was very helpful :)

[@BackToBackSWE]

Thanks! why dont you try our 5 day free mini course backtobackswe.com/

[@Series0Tubes]

Thank you for making this video!

[@BackToBackSWE]

Sure

[@superchillh3o]

You are an excellent teacher, thank you

[@BackToBackSWE]

sure

[@sgbalakrishna]

Thank you so much you teach really well!

[@BackToBackSWE]

Glad it was helpful!

[@chtruckerhat]

youre actually such a good teacher man

[@BackToBackSWE]

thanks

[@purovenezolano14]

Great stuff. Thanks!

[@BackToBackSWE]

sure

[@ghazalsahebzamani4925]

Very helpful!Thank you very much!!

[@BackToBackSWE]

sure, thanks for watching

[@zzzz26526]

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.?

[@jobomathaha7420]

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

[@supamdeepbains5172]

You're videos are really helpful

[@BackToBackSWE]

Thanks

[@chughgaurav]

Amazing explanation :)

[@venkatachengalvala4289]

Minor mistakes but well-explained and really enthusiastic! :)

[@kennethochieng37]

You are a talented teacher!

[@BackToBackSWE]

thanks

[@JacobCritch]

Incredible explanation. Very passionate 👍. Needed a refresher on this before Amazon interview.

[@BackToBackSWE]

nice

[@JacobCritch]

@@BackToBackSWE Failed cause they asked me binary search 😂😂

[@AkamiTenzuo]

Best explanation ever!

[@Iam_number_one]

thank you so much ; you're the man .

[@fantasy9960]

wow thank you! You explained the concepts so well and clearly!

[@azzzydzz]

Legend man! thanks!

[@sarahebal4391]

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

[@shwetadk1986]

Love your videos !. Hey can you please do a video on Course Schedule - Leetcode problem 207

[@BackToBackSWE]

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.

[@deanhunter6304]

Amazing explanation!

[@BackToBackSWE]

thx

[@ZNhatAnhZ]

really helpful man!!

[@BackToBackSWE]

thanks, glad it helped

[@grunze]

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.

[@BackToBackSWE]

nice

[@sumansantra777]

Thank you a lot Dude for helping backbenchers like me. :)

[@BackToBackSWE]

ur gud

[@fuckooo]

Nice channel bro, subbed!

[@BackToBackSWE]

yoyo

[@syedrizvi2687]

Thank you so much

[@vimalk2661]

If I need some explanation . I look for your videos man. That's the end point for me, I just get what I need.

[@BackToBackSWE]

great.

[@jagicyooo2007]

Goes deep and comes back out!

[@BackToBackSWE]

ok

[@TheA7xaddicted]

you just saved my degree man :') bless

[@The8merp]

between the recursive and stack approaches for DFS, when should we use which and which is better in terms of time and space complexity

[@BackToBackSWE]

both are the same in time and space, the explicit stack just uses a stack in memory, the recursive uses the literal call stack to hold state (which is also a stack stack)

[@jit3191]

Great Explanation, will you be able to do a video on Topological Sort, please

[@BackToBackSWE]

thanks and we have that on backtobackswe.com (paywall)

[@robertrey7002]

great stuff man

[@BackToBackSWE]

thanks

[@guoqiangliu6884]

wonderful job!

[@BackToBackSWE]

thanks

[@miaboloix1737]

Question: In an interview, what is the benefit of keeping a "seen" HashSet to keep track of visited Nodes vs. potentially defining the Node class to have a "visitited" boolean field and just toggling it?

[@BackToBackSWE]

Ultimately whatever works works. But that would be a bit odd since "seen" is not inherent to the data type and its purposing. As a programming choice that'd seem odd? Otherwise, whatever

[@3Deviant_]

I would say it is better because what if the graph is giant, like 10^10 amount of nodes. When this search starts the visited array would be empty, whereas the other binary flip method will add that small amount of space taken up by the bit by the amount of nodes there are. So lets say a binary flip takes up 8 bits and there are 100 nodes. 8bits*100 space is taken up right away from the start. While the array method is still very small when it starts space wise since its empty.

[@jordanrectan4793]

14:59 that is what she said! great video, thanks a bunch!!

[@journeytowardslife9830]

Great video ! I had one doubt , what if the graph had duplicate elements ? Since we use set , if there is one element say c and it's already seen and if there is another c , then it won't be processed right ? What to do in that case ?