Breadth First Search (BFS): Visualized and Explained
Vložit
- čas přidán 12. 06. 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.
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.
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!!
Hands down best vidoe on youtube for learning this!
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
The ball and string analogy alone was enough to get me to like the video :D
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.
BEST CODING VIDEO I HAVE EVER WATCHED! So elegantly explained, thanks so much!!! 🙏🏻
The work you are doing here is fantastic, hope all the best for you man, thanks a lot
your way of teaching is absolutely amazing
Glad you enjoyed it!
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.
Such well organized content and finely polished presentation. Instantly subscribed. Appreciate the effort!
Love these videos! Really interesting topics and they’re super easy to follow
I love the music, so relieving, make me concentrate on what you are talking about.
This channel is a gold mine!
@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 :)
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!
Amazing Content Sir,like no one else in Computer Science Domain. Really Appreciate you animation,background music and hardwork you put in every video❤️😁❤️
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
Beautifully explained ! Keep up the good work.
Absolutely stunning! Love the animations and the intuitive vibe just like 3b1b;
The flood fill problem is a great example for the use of graph traversal algorithms! Definitly going to show it to my students.
Again an awesome explanation by Reducible
I am addicted to such content. Plz if someone else also creates such content pl tell.
Ur videos make maths so beautiful. Hats off👏👏
Beautiful and clear explanation! Thank you so much!
This is incredible, I cannot thank you enough!
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
The quality of this channel is incredible. 3blue1brown level.
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.
really great contents, I really understand a lot from your videos!
*Keep it up*
Your explanation was so good, thank you very much, keep doing these kind of videos bro!
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
Wow, that's a very cool explanation! I think I understand it much better now, thx!
such a clear and detailed explanation 👏. Thank you 😇
absolutely loving your content - great stuff
That's a great efford! I wish I discovered this channel earlier. Thanks
Awesome Content, Please add more such videos, Graph and DP would be Awesome.
This was so insanely good! Although I watched the video a few times. I could understand everything!!
This video is absolutely amazing!! Thank you!!
This problem seems like a building block to solve graph problems. Thank you for sharing this.
You deserve much more subscribers.
amazing!!! helped me a lot, as a junior that is just introduced to this topic
That level explanation. Awesome!
that was eazy, simple, adorable !
You guys deserve so much more subscribers
This channel is so much underrated
Oh yeah
This is definitely the one
It’s been years since my undergrad and this helped me review thank you so much
this is the best. i beg u not to stop
Very nice video, thank you!
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.
Excellent content - thank you.
Please please please keep uploading videos ... they are soooooooo good .....
man i'm new to the channel and am lovin it
I might have been traversing the internet the DFS way, that's why I found your channel so late!
was fluent explanation thank you
it helps me a lot!!!
Amazing vid, amazing channel
Bro , You are just tooooooooooooo good , please make more algorithm videos
CZcams is indeed full of gems.
Wow man. Love you
great Job , Thanks A lot.
hope more graphs algos in the future
I still love you man!
Thankyou.
legend
very good vide;)
I just watched this video after I intuitively found by myself an algorithm to capture a group of stones in a GO game setup
Best one
Perfect
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
I was wondering to know what software did you use for the graph animations?
Gold
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 CZcams for free :P
@@Reducible Yeah you can! That would be the best thing! But like can you do them simultaneously and in one video
Wow, how lovely you accent is😇.. damn to Hindi accent!
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])
Here before 1k views.
👍
Is this better with sets for v instead of a list?
around 6:30, you said (row, col): (2,2). but it seems like (3,3). what am I missing here?
I'm just here because I really like lines and stuff
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
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?
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.
Can anyone send me this grid problem code in cpp
Btw Do you also you Manim Library of Python?
Its literally in the discription
thumbnail looks like the reverse transmutation circle from FMAB
0:14
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)]
this is the island problem right ??
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.