Kruskal's algorithm in 2 minutes
Vložit
- čas přidán 24. 11. 2012
- Step by step instructions showing how to run Kruskal's algorithm on a graph.
Code: github.com/msambol/dsa/blob/m... (different than video, I added this retroactively)
Source: Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani [www.amazon.com/Algorithms-San...]
LinkedIn: / michael-sambol
Are you from outer space? My lecturer couldn't explain this in 2 hours and you did in 2 mins. Thanks a lot.
Math and CS educators need to work backward from this video. Have the students obtain an intuitive understanding of what's going on, and then drone on for 2 hours. Hopefully, something sticks. Way to go, Michael!
@@Fedorahatter exactly, my professor talked about bunch of lemma and proofs first and then go on briefly touched upon the algorithm which we were all lost by the time he talked about it which was like 1 hour into the lecture.
Same, this video is much better than my lecturer explaining this topic in an hour still I didn't understand. I wish he'll explain like this.
Fr me as well.
😆
you explained something in 2 minutes what my prof did in two lessons.
Elmir Ma Glad I could help!
+Elmir Ma Same thing here.. I've wasted my time at class lol
Griffin Seannery and I ended up doing well in that class. Thanks again, uploader!
@@Elmirgtr Some stories have fairy tale endings.
@@school_pizza So true. When I wrote this I was in undergrad, now I am doing PhD and working on a paper to submit to Nature
“If you can't explain it to a six year old, you don't understand it yourself.”
Thank you so much, we were given incomprehensible pseudo-code and confusing notation. For this to seem so simple after a
+Richard Paul You're welcome, Richard. Glad you enjoyed.
i hate discrete math with passion. making something simple look so complicated
@@08a14979 lmao im genuinely worried im going to fail discrete math. I swear it’s how my professor teaches. He overcomplicates everything and he will talk about one thing for like an hour so it’s too easy to get confused.
It's incredible how my teacher's lessons started talking about cycles and cuts and shit formulas while the algorithm is so freaking simple... Order edges by weight, go through them in that order, if the edge connects different trees use it, if it connects the same tree discard it, was that so difficult? Thank you for this clear explanation dude, you rock
ele deu gosto porque é bueda da fixe
0:56 - "Notice the smallest edge is BE, but this node connects 2 nodes that are already in the same tree, so it will not be chosen."
I think you could have picked your words better. The reason we don't choose BE is NOT because B and E are already in the same tree (I mean, so were A and C, yet you added AC), but because adding BE would create a cycle in the tree, and MSTs aren't supposed to have cycles.
You cleared my confusion. Thank you.
how is that confusing? if both points are already discovered then u arent adding a new point to the tree... its just a wasted edge
@@keagenmccartha7412because he did that with AC even though both were already in the tree. Just because you are r€t@rded doesnt mean you need to yap about it to everyone else.
@@keagenmccartha7412 because "A spanning tree of a graph consists of all nodes of the graph and some of the
edges of the graph so that there is a path between any two nodes"
@@anirudhkrishna.s5397 congrats genius
Fucking legend mate!
tfw: this is actually really simple but your professor unnecessarily complicated it
Fast, clean, and with a good example. Quality work, you did good. Thank you.
Thanks - this was concise and helpful. It cleared up my confusion of whether the tree must be connected from the beginning or not.
Your tutorials are the best! I learned 2 months of discrete mathematics in under 30 minutes. 5 years have passed since you posted this but it has had a larger impact on my understanding than my professor has provided all semester. Thanks.
you're making those kind of how to-videos everyone is looking for, a good explanation with no annoying blabla, thank you!
Absolute Chad ; Saving me from my algorithms exam tomorrow.
My Lecturer took so much explaining these concepts but you are a genius made it easy in no time.
Cheers !
4 hours of discrete mathematics lectures and seminaries ... compressed in 2 minutes. you sir, are a life saver
Very nice video. Straight to the point and quick.
because of your videos, I learned Kruskal's and Prim's algorithms in 4 minutes. My teacher took 10 minutes to do an example of Prim's and I didn't even understand it then. thanks!
Thank you so much for this, my professor didn't even explain a thing but included this in the midterm I'm having in 13 hours. You're a lifesaver.
you are my time saver, I spend many hours on PPT, blog and other videos, none of them explain so clearly in this manner. they try to be professional so that they don't speak nature language. Thank you very much.
The explanation is very intuitive and concise, thank you so much.
Your material is simply excellent! I can't wait for more!
This was way easier than my prof's explanation. Thank you so much!
Dude I spent a whole lecture not understanding and it's actually this straight forward
Great stuff man,,, crisp and precise... never going to forget Kruskal's algo now
You are awesome. Seriously you taught a whole book chapter in just two minutes. 👍🏻
Perfect tutorial I have ever seen. Thanks, I got it in just 2 minutes!
Short, simple and clear. Good work !!
Many thanks to you
Michael, your vids are so succinct and effective.
Concise and easy to understand, many thanks, Michael.
Even in 2021, you are still relevant. Thank you for your service
You're a lifesaver! Got an exam tomorrow and my textbook nor my professor was making sense to me. Glad to know it was a much easier process than I initially thought!
he's saving lives still... been 6 years!
Sir you are the Best!!!!!!!
The shortest and meaningful video that can be created!!!!
Thank you SO much!!!!
my god man you are amazing, you just explain it without taking 10 years THANK YOU
Thanks!!! You literally saved me ... and my exam's tomorrow! You explained something in 2 minutes when in class it took like 2 hours!
Simple and straight to the point. Thankyou so much!
This saved me so much time. Very clear and informative video, thank you!
i liked the way you guys explain it, shor and clear.
It would be cool if you added a short video about union and find as an addition to this video, as the intuition for Kruskal's algorithm is explained brilliantly here, but the implementation needs to use union and find for the complexity to be as good as you mention and these functions are quite interesting and not completely trivial.
Thanks for all your great videos btw, they are very clear and concise :)
Very succinct and to the point. Thanks for this.
Really saved my day after spending hours in the text books to understand this. Thanks a lot!
Short and comprehensive... Great job!!!
This was beautifully done, thank you!
Great video. Thanks so much for making it!
Thank you so much. This is the clearest explanation I've seen
Thank you!! Excellent explanation contrary to the million slides in my notes that are just plain confusing.
Ohhh I never knew that the arcs should only add new nodes, I was only taught that it should not create cycles. This makes it a lot easier. Great vid mate
Saved me so much time. Thank you for great videos.
Short and clear review, thanks 👍
Saved my life on the exam morning!
Thank you so much :D
For those who are a bit confused, he did not search for 7 by skipping 4, 5, 6. He did in fact search for them but found them to be making a circuit (closed path with previously chosen nodes).
You just said he didn’t
Straight forward👏🏼nice one
short and sweet i like it. Keep up the good work!
You are a LIFE SAVIOR. Thanks!
Thanks man! Just as your video on ford-fulkersons algorithm, simple and straight forward. Cheers
This is amazing, love this channel! Thank you :)
Thanks for helping, got a test today and explained much better than my professor. Thanks a lot :D
I wondder WHY at university they spend 20-30 minutes explaining this, and having round of questions. Your 2 minute videos explaining algorithms are simply PERFECT. Thank you very much indeed.
Thanks a lot for this short explanation!
I did not think it was possible. Nicely done
Excellent explanation!
amazing, just what i wanted and needed
Thank you!! You are an amazing person! You made it so simple! x
excellent work, man!
what a fantastic video. seriously this is a great explanation shrunk to a 2 min video
Ran across this video again during my university algorithm course studies. Thank again Mike!
Boom! Awesome. 💪🏼❤️
always awesome algo
You're amazing. Thank you !
I just love that you simply get to the point.
Thank you!
@@MichaelSambol és bueda da fixe
Hi I have a final exam CS 1332 tomorrow morning and your video helped me a lot. Thanks so much and go Yellow Jackets!
Great explanation, thanks for this.
This channel is the best. I wish I watched these in college. Please make more videos on algorithms topics!
sir thank you ! it's very clean and understandable explication !
Very nice! Thanks from Munich.
I love you vids, really helpful, keep it up.
Still relevant in 2021. Thank you!
ele deu gosto porque é bueda da fixe
You're awesome dude, great vids
wow, that is a really nice explanation, thanks for sharing!!!!
Awesome explanation ever!
Simple and no bullshit. Love it!
summer test tomorrow for my discrete math class, ur a hero
Very intuitive, thank you!
Generational help done by u 😭🛐
Thanks fam, your review and example vids are dank af
haha didn't think I'd see the word 'dank' uttered in the comment section of an algorithms review video...classic
Ryan Davis ayy got a 7.7 / 10 partly thanks to this guy
thank you bro, you are the real man
Great video, thanks!
what amazes me is how I seat through 2 hour of lecture class and couldn't understand a jack thing but 2 minute video and I feel like replacing my professor so I can teach the class.
Same
I would still suggest staying in lectures.
For instance, this videos states that you can use merge sort to sort the Edges. Which is fine and true, but why would you even bother? Why use merge?
Why not a priority queue?
He also doesn't explain the time complexity. You can perform Kruskal's in O(ElogV) but his is O(ElogE) because merge sort is dominating. Which is better? [Most examples show E >= V].
These videos are great for getting the point and quickly understanding how it works, but when you get into it the details may not be as good as you'd think.
@Rrestoring faith Exactly. This video doesnt actually teach you anything. It simply shows what Kruskal's aglorithm is. This is way too basic to be useful
thank you so much, you helped me a lot because I will have a test about this algorithm.
The best tutorial ever
This is great, best Math video on CZcams.
perfect explanation
Thanks Mike!
Quick and simple, thanks!
Thanks for making it simple !!
u help me alot man .. good jobb broo
thanks dude!! Good work!! :D
Precise and perfect
Thank you for the video!
Saved my life. Subbed
dude your saving lives here
precise and concise
Thank you so much.