Breadth-first search in 4 minutes
ฝัง
- เผยแพร่เมื่อ 8 มิ.ย. 2024
- Breadth-first search in 4 minutes.
Code: github.com/msambol/dsa/blob/m...
Sources:
1. Introduction To Algorithms, Third Edition (CLRS) [www.amazon.com/Introduction-A...]
2. en.wikipedia.org/wiki/Breadth...
LinkedIn: / michael-sambol
![[Live] : ONE 167 วันนี้!! "ตะวันฉาย vs โจ"](http://i.ytimg.com/vi/D9_dvfIa6Ao/mqdefault.jpg)
![ไม่ต้องมีที่ที่ให้ฉันอยู่ แต่ขอแค่มีฉันอยู่ก็พอ (Spaceless) - getsunova [OFFICIAL MV]](http://i.ytimg.com/vi/4N8idbxZ-7M/mqdefault.jpg)
After I made the video, I changed the code in GitHub to use a deque instead of an array for the queue. This allows us to pop the first element in 0(1) time. More here: wiki.python.org/moin/TimeComplexity.
Good video
I love that your slides are so minimalistic, for me it's the perfect amount of content to support what you say
It's good to see that you are back. Your past videos have helped me a lot, thank you.
I have an algorithm test coming up on graphs and this came out at exactly the right time! Thank you!!
You are literally saving my life! I’m so glad that you’re uploading again!!
Thank you for your quick illustrations! I enjoy your videos a lot.
Wow, you've added so much value in such a short amount of time. Thank you sir!
Great video. Makes the concept very easy to understand. Thank you for the way you made it.
your videos keep me sane i swear
That is so concise! Perfectly explained!
thanks!
You deserve more views, thank you for your videos
you are literally helping me to survive my exam :) big thanks
Damn because of your videos, I managed to prepare for the exam tomorrow. I had no idea how I was going to get through so much material in one day, thank you.
Clear and straight forward. Thank you.
very useful and straight to the point, it was useful thanks!
Best Explanation on youtube so far..Every other video is from 15 to 20 minutes..and here you are doing it in 4 minutes😂
This video is well-explained.Thanks a lot for this ....
Thanks, you literally saved my life.
thank you so much for explaining this in less than 5 min
I learned more in 4 minutes than all the 30 years of my life
Michael Sambol should take the place of my tenured professor that teaches Algorithms.
This man does not miss 🔥
The Queue in place always go over my head, now with the visualisation it makes it a lot more easier and obvious 😅😅😅
Dude you are the best, cheers
thank you so much for clear explanation
You saved my entire life. Thank you so much.
💪🏼❤️
Legit the best explanation out there.
Thank you!
thank you, so much easier to understand
Why do you need "visited" queue? It can still work without it, doesn't it?
UPD: just figured out that your algorithm is for general graph, but you apply it to a tree (special case of graph) so "visited" is redundant for tree case.
Ive been using recursion in dfs thinking it would work here too
Thank you for helping me realize my mistake
Def easier iteratively for BFS! github.com/msambol/youtube/blob/master/search/breadth_first_search.py
Thank you for this videos
thank you for your clear explanation
You're welcome!
Bro, you are a god of explaining and teaching, so quick, so simple, so smart, not like other teachers who sound like broken records and x2 speed you tube videos.
Thank you, Marian!
Thank you for the vide! What is the addrd value of the last if statement
You say first in first out like we are supposed to know where you put elements in and out, can't you put them in either at the top or at the bottom? And why do you say vertically and horizontally without showing a tree, the orientation can be different, we have to fast forward to see what tree you have in your mind, but we can't read yours
Could you please make a video on the Hungarian Method for a bipartite graph, using only the graph? Or is this not a subject you can cover?
I'll add it to my list..
Great.
i love you so much and i hope you live a long happy life
ty very muchh
Thanks
great video my
Why not make "visited" a property of the node object so you don't have to create a separate 'visited' array?
what if you have to run more than one search on the same set of nodes? you would have to traverse the entire tree twice to reset your nodes for a single search. with an array you can just clear it. Much easier.
I love you!
you mentioned the use of queue, but used a stack with pop function, no?
The concept is the same where the abstract data structure is a queue, i.e., FIFO. In the video I used an array and did pop(0), but I later switched the code to use deque and popleft() [same concept as pop(0)] because it's more efficient. See here: github.com/msambol/youtube/blob/master/search/breadth_first_search.py#L17-L19.
Let me know if that doesn't make sense!
1:31 isn't the que popping 'C' first ?
would be easier if you add what is the front and what is the end of the queue because other examples and other i see the queue is other way. I mean it doesn't matter since i figured it out after a few minutes but i think it would make it easier to understand quickly whats happening lol
I should have added that, you're right. Apologies!
@@MichaelSambol no worries just reviewing for algorithms test tomorrow And this really did helped me. Thanks for making these videos!!!
Respect 🫡
🫡
And what are you searching for in there?
The letter X
Hi, the audio is not clear on your videos. It goes on mute in between for a few seconds. Could you please fix this on all your videos. It would be really helpful. Thanks.
Sorry about that. I'm working on the right settings. Thanks for the feedback.
Is my latest video better, on Fibonacci heaps?
@@MichaelSambol Nope. It isn't any better. Fibonacci heaps also has the same issue.
Confusing how you pop the [0] element yet you show that element as being on the far right of the array order, which would not be the [0] element in actual code...
Sorry that's confusing! Check the latest code here, I hope it clarifies it: github.com/msambol/dsa/blob/master/search/breadth_first_search.py.
Muhammad Sumbul 😳😳
What happens if the graph in question contains cycles? If we're marking nodes as visited when we pop them, won't that mean there will be multiple instances of a node being enqueued into the queue until they are actually reached and dequeued i.e. marked visited?
My lord. Sometimes play back speed 2x just isn't enough
Use revanced there is 5x
Maybe stop watching tik tok so you have an attention span longer than a minute
@@legolorian3271 he does talk pretty slow I won’t lie.
o nanq
First
you code has issues i think this is the right way for BFS
def bfs(graph, node):
visited = []
queue = []
visited.append(node)
queue.append(node)
while queue:
s = queue.pop(0)
print(s, end=" ")
for n in graph[s]: # Corrected indentation
if n not in visited:
visited.append(n)
queue.append(n)
Definitely a few different ways to do it. See here: github.com/msambol/dsa/blob/master/search/breadth_first_search.py
Thanks for your clear explanation