Breadth First Search (BFS): Visualized and Explained
ฝัง
- เผยแพร่เมื่อ 13 พ.ค. 2024
- In this video we break down the BFS algorithm in a visual manner with examples and key intuition. We then show the implementation of the algorithm with code and then finish off the video by demonstrating how you can use the BFS algorithm to solve the Flood Fill problem.
0:00 Introduction
0:45 BFS Intuition/Examples
2:39 BFS Implementation
5:19 Flood Fill Problem
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
Lift Motif by Kevin MacLeod is licensed under a Creative Commons Attribution license (creativecommons.org/licenses/...)
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
All other music by Aakash Gandhi
Hey everyone, quick channel update: this channel recently hit 1K subscribers! Thank you all for your support and kind comments on all my videos. I got a lot of ideas for interesting content in future videos so stay tuned (hit that subscribe button)! As always, thanks for watching!
really good content, would you consider making a video about A* algorithm and topological sort, also maybe some data structure like red/black tree, segment tree, I'd be watching them!
Please make more videos ,really great channel and content
What? 6 month ago you had only 1k subs? Unbelievable
please, do more videos. it's much more interestring than reading books
We certainly need more videos from you on the topic (GRAPH)
Love the 3blue1brown vibes. This is the best way to learn for me and you do a great job explaining everything.
Nice profile picture.
I do wonder what the software is though
He is the 3b1b of Computer Science.
heyyy a 3blue1brown fan.. hard to come by
@@andrewprahst2529 The animation is made through python manim library created by 3b1b
This is amazing content! I'm a high school student who loves computer science, and this is just amazing. I know a lot of effort must have gone into these videos (what with having to learn manim and everything), I hope you continue into the future
Thanks for the awesome comment! And yeah, these videos do take a lot of time and effort, but it's a lot of fun for me so I plan on continuing for the foreseeable future!
Same , do you do competitive programming too?
@@AkshatSinghania yep!
I must say, this is one of the most effectively explained videos for DS & Alogs. Even though video is around 10.40 minutes, it's well ordered, planed and well explained to the point. Recommend this channel to anybody, who is looking for a quick but more elaborated explanations on Data Structures and Algorithms.
I finally understand BFS!! THANK YOU SO MUCH. That ball and string intuition piece made my mouth drop. And I finally truly understand a flooding algorithm - how why and when to use it. THANK YOU!!
Another highly polished video. You deserve so much more subscribers (sickening to see only 1k subscribers for such high quaility content). You are 3Blue1Brown
of computer science for me and hopefully you get millions of subscribers like him.
Hands down best vidoe on youtube for learning this!
Your graph theory series is amazing, I wish there was more to this series with more advanced topics! only thing I would like to point out is that you can mark vertexes as visited right after pushing them to stack/queue, Because you can be certain that if a vertex is in the stack/queue it is waiting to be visited , this avoids unnecessary insert/remove operations on stack/queue.
I wish if you were my DSA lecturer, just came across you channel I wish if i knew your channel a year ago. Keep making these high standard videos. Would love to see a whole series about Data Structures and Algorithms.
The ball and string analogy alone was enough to get me to like the video :D
The work you are doing here is fantastic, hope all the best for you man, thanks a lot
Such well organized content and finely polished presentation. Instantly subscribed. Appreciate the effort!
BEST CODING VIDEO I HAVE EVER WATCHED! So elegantly explained, thanks so much!!! 🙏🏻
This channel is a gold mine!
this is amazing, thank you for making them. These videos are timeless, people will be coming back to them in 2 years
Glad you enjoyed it -- thanks for the awesome comment.
@@Reducible he was right, great content
@2:39
So so so so so so so helpful to actually have a visualized explanation of the implementation of the codes!!
Thank you so much!! You are absolutely brilliant :)
The flood fill problem is a great example for the use of graph traversal algorithms! Definitly going to show it to my students.
Love these videos! Really interesting topics and they’re super easy to follow
This is incredible, I cannot thank you enough!
Absolutely stunning! Love the animations and the intuitive vibe just like 3b1b;
I love the music, so relieving, make me concentrate on what you are talking about.
I really do appreciate your graph theory videos they are really clear and I love the way you are making me think about the problems and solutions. Please make more videos about graph theory and maybe showing some examples of problems solved with graph theory
your way of teaching is absolutely amazing
Glad you enjoyed it!
Beautiful and clear explanation! Thank you so much!
Excellent explanation and example. Love it when you mention the real life example of the “Fill” button in Paint🎨 app, it gave me a instant picture of BFS.
Beautifully explained ! Keep up the good work.
Thankyou so much for this video!! This is awesome. Today my DS teacher gave me the same problem and voila! I got you.Thanks✌🏼, You cleared my confusion!
Oh yeah
This is definitely the one
It’s been years since my undergrad and this helped me review thank you so much
I am addicted to such content. Plz if someone else also creates such content pl tell.
Ur videos make maths so beautiful. Hats off👏👏
The quality of this channel is incredible. 3blue1brown level.
Amazing Content Sir,like no one else in Computer Science Domain. Really Appreciate you animation,background music and hardwork you put in every video❤️😁❤️
Just want to say this is a fantastic explanation!! I am taking cs50ai and the first problem is the use BFS to find the shortest path between two actors and I just solved it thanks to this video
Again an awesome explanation by Reducible
such a clear and detailed explanation 👏. Thank you 😇
That level explanation. Awesome!
absolutely loving your content - great stuff
really great contents, I really understand a lot from your videos!
*Keep it up*
That's a great efford! I wish I discovered this channel earlier. Thanks
Your explanation was so good, thank you very much, keep doing these kind of videos bro!
This video is absolutely amazing!! Thank you!!
this is awesome man! it has a clear explanation with pseudocode easy enough to understand and make an implementation thanks!!
lol that was python, great to do pseudocode I guess
Awesome Content, Please add more such videos, Graph and DP would be Awesome.
amazing!!! helped me a lot, as a junior that is just introduced to this topic
You deserve much more subscribers.
This was so insanely good! Although I watched the video a few times. I could understand everything!!
Wow, that's a very cool explanation! I think I understand it much better now, thx!
this is the best. i beg u not to stop
This channel is so much underrated
This problem seems like a building block to solve graph problems. Thank you for sharing this.
You guys deserve so much more subscribers
Excellent content - thank you.
Very nice video, thank you!
I might have been traversing the internet the DFS way, that's why I found your channel so late!
Absolutely amazing. Please make as many videos as you possibly can on graph theory. I'd buy a complete DSA course from you if you choose to make one.
Please please please keep uploading videos ... they are soooooooo good .....
it helps me a lot!!!
Bro , You are just tooooooooooooo good , please make more algorithm videos
was fluent explanation thank you
man i'm new to the channel and am lovin it
very good vide;)
Amazing vid, amazing channel
Wow man. Love you
great Job , Thanks A lot.
I still love you man!
TH-cam is indeed full of gems.
Thankyou.
legend
Perfect
hope more graphs algos in the future
Best one
I just watched this video after I intuitively found by myself an algorithm to capture a group of stones in a GO game setup
I recognize that the only difference in the two algorithms (BFS vs DFS) is that BFS uses a queue vs DFS uses a stack. But you presented a really clean algorithm using recursion in DFS. Can BFS be reduced down to a recursive form too?
Well, it's always possible, but it really doesn't make sense to use recursion since DFS recursion is just using the call stack. Recursion implicitly uses a stack. BFS uses a queue which is basically the opposite of the stack so it really doesn't fit the recursive framework. See this for a more thorough discussion and some of the possible ways: stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively
Curious why you didn't just use a min/max function with neighbors to avoid boundary issues? Wouldn't that be a simpler implementation?
i wish i watch this video before I build my minesweeper game if so I wouldn’t have a hard time figuring out flood fill on my own
btw I think the isValid function can be write like this
def isValid(img, row, col):
return row in range(len(img)) and col in range(len(img[0])
cool intro
Can you please develop a course comprising on data structures, algorithms and problem solving paradigms??
Or ... I could just make a course equivalent series of videos on TH-cam for free :P
@@Reducible Yeah you can! That would be the best thing! But like can you do them simultaneously and in one video
I was wondering to know what software did you use for the graph animations?
Gold
Here before 1k views.
When you have shoe laces and need to tie them
Hello.... Thanks for creating your content.. however, I realized that in your animation, while visiting vertex 3, you added 2 to the queue.
However, 2 is adjacent to vertex 0, therefore, it would be visited at the same level with vertices 1, and 3. Therefore, adding it into the queue would result into revisiting of the vertex, which isn't efficient
Is this better with sets for v instead of a list?
Wow, how lovely you accent is😇.. damn to Hindi accent!
around 6:30, you said (row, col): (2,2). but it seems like (3,3). what am I missing here?
Hi :D
Thanks for the video :D
How can we use the BFS implementation focused to Objects in Python? The Atributes of the Objects needs to indicate the neighbors that the object have ? :O
Its really interesting :D How do u use this algoritms in a programing language ? :D
Thanks a lot :D
9:32 havent you alredy changed the value of the of the starting pixel, and later pixels wont match it?
I'm just here because I really like lines and stuff
👍
It's been a long time since I took algorithms, but I think we skipped BFS in general and went straight to Dijkstra's algorithm.
Btw Do you also you Manim Library of Python?
Its literally in the discription
Can anyone send me this grid problem code in cpp
thumbnail looks like the reverse transmutation circle from FMAB
this is the island problem right ??
If you code in Python, never initialise a list as [something]*N, because it will create a list with N the same objects, which will break your program. Instead, use [False for _ in range(N)]
Is this channel related to 3blue1brown?
Directly, no. I love his work and I think his channel is one of the best educational channels out there. I use the same animation library he uses so I guess the content will have a similar style in that sense.
@@Reducible please can you make a documentation of manim? it is very difficult to work with it .
Can you tell how do I label points marked on a 2d graph.
B - Boss
F - Fighting
S - Stages
I've been using variants of this algorithm for years. I never thought I had invented it first... but knowing it for sure is still somewhat disappointing.
0:14
can you make more leetcode solution videos please?