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

preview_player
Показать описание
📹 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

++++++++++++++++++++++++++++++++++++++++++++++++++

Рекомендации по теме
Комментарии
Автор

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.

BackToBackSWE
Автор

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

taiwan.
Автор

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

pranitachikorde
Автор

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!

reedmurphy
Автор

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

AdityaMishra-veyu
Автор

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!

historian
Автор

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.

mouseclicker
Автор

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

AH-xbeb
Автор

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

alanwang
Автор

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

Labattfartoui
Автор

Not all heros wear cape. This guy is JUST AMAZING.. He is a REAL HERO..!!

Word out there needs to know about this guy.

RajSehmi
Автор

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.

DanielDiaz-rqko
Автор

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!

Acroft
Автор

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.

abdulmalikquadri
Автор

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!

chrisbaca
Автор

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.

metarun
Автор

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.

qingtianwang
Автор

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

Maca-cs
Автор

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

metehanemir
Автор

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

joy-smsl