No video
Kruskal's algorithm in 2 minutes
Step by step instructions showing how to run Kruskal's algorithm on a graph.
Code: github.com/msa... (different than video, I added this retroactively)
Source: Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani [www.amazon.com...]
LinkedIn: / michael-sambol
Пікірлер: 425
Are you from outer space? My lecturer couldn't explain this in 2 hours and you did in 2 mins. Thanks a lot.
@peterbakke
6 жыл бұрын
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!
@diwang4572
3 жыл бұрын
@@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.
@mavyfaby
2 жыл бұрын
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.
@adelalmohtaseb5261
Жыл бұрын
Fr me as well.
@danielriley3618
Жыл бұрын
😆
you explained something in 2 minutes what my prof did in two lessons.
@MichaelSambol
9 жыл бұрын
Elmir Ma Glad I could help!
@Griff10poldi
8 жыл бұрын
+Elmir Ma Same thing here.. I've wasted my time at class lol
@Elmirgtr
8 жыл бұрын
Griffin Seannery and I ended up doing well in that class. Thanks again, uploader!
@school_pizza
4 жыл бұрын
@@Elmirgtr Some stories have fairy tale endings.
@Elmirgtr
4 жыл бұрын
@@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.”
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
@miguelflor1600
Жыл бұрын
ele deu gosto porque é bueda da fixe
Thank you so much, we were given incomprehensible pseudo-code and confusing notation. For this to seem so simple after a
@MichaelSambol
8 жыл бұрын
+Richard Paul You're welcome, Richard. Glad you enjoyed.
@08a14979
6 жыл бұрын
i hate discrete math with passion. making something simple look so complicated
@biblemansings
Жыл бұрын
@@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.
tfw: this is actually really simple but your professor unnecessarily complicated it
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.
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).
@brettsharpe7305
7 ай бұрын
You just said he didn’t
@JJCUBER
4 күн бұрын
@@brettsharpe7305the second part where they say that they did search refers to the rest of the numbers. In sum, all edges were considered in increasing order, but the ones which would create a cycle were discarded.
Fucking legend mate!
4 hours of discrete mathematics lectures and seminaries ... compressed in 2 minutes. you sir, are a life saver
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.
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.
@kirandhakal8601
4 ай бұрын
You cleared my confusion. Thank you.
@keagenmccartha7412
3 ай бұрын
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
@squeesquee6
3 ай бұрын
@@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.
@anirudhkrishna.s5397
2 ай бұрын
@@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"
@keagenmccartha7412
2 ай бұрын
@@anirudhkrishna.s5397 congrats genius
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 !
Very nice video. Straight to the point and quick.
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!
@Dorddis
Жыл бұрын
he's saving lives still... been 6 years!
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.
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!
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.
@mariestolk3794
4 жыл бұрын
Same
@rrestoring_faith
4 жыл бұрын
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.
@theendurance
4 жыл бұрын
@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
I just love that you simply get to the point.
@MichaelSambol
3 жыл бұрын
Thank you!
@miguelflor1600
Жыл бұрын
@@MichaelSambol és bueda da fixe
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
The explanation is very intuitive and concise, thank you so much.
From what I've learned: If you are stuck between choosing multiple edges with the same weight, like in 0:40, (A, D) or (A, C), or (B, E) Choose the one that doesn't create a cycle, if none of them create a cycle: Prioritize the edge that is alphabetically first. In this case, (A, C) is the first in the alphabetical order.
Even in 2021, you are still relevant. Thank you for your service
you're making those kind of how to-videos everyone is looking for, a good explanation with no annoying blabla, thank you!
My professor took over an hour trying to explain Kruskal's algorithm. You did it in less than 2 minutes. Someone tell NASA to hire this fucking man!
Perfect tutorial I have ever seen. Thanks, I got it in just 2 minutes!
Seems simple enough.. but not so simple for coding :P
@MidnightBloomDev
4 жыл бұрын
You could do this with 10 lines of python code
@vtvtify
4 жыл бұрын
@@MidnightBloomDev Ummmm, despie it indeed being simple to code, just the union find used is not 10 lines...
@isakjacobsson867
3 жыл бұрын
This is a one liner ez
@Hgh38
2 жыл бұрын
Nah once you implement these things, it gets easier. I lowkey love to do it.
Still relevant in 2021. Thank you!
@miguelflor1600
Жыл бұрын
ele deu gosto porque é bueda da fixe
Thanks - this was concise and helpful. It cleared up my confusion of whether the tree must be connected from the beginning or not.
my god man you are amazing, you just explain it without taking 10 years THANK YOU
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 :)
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 a LIFE SAVIOR. Thanks!
Sir you are the Best!!!!!!! The shortest and meaningful video that can be created!!!! Thank you SO much!!!!
Great video. Thanks so much for making it!
Ran across this video again during my university algorithm course studies. Thank again Mike!
@MichaelSambol
9 ай бұрын
Boom! Awesome. 💪🏼❤️
I hate when my university professors start by explaining abstract shit and formulas and general cases, u fall asleep, and in the and they say aaalll this just to remove all possible edges. I mean they could start with catching your attention with an example, and then expand on the subject for 3 hours. It would be so much better.
@Abdullah-cm1tn
3 жыл бұрын
yes, they don't start with examples. they start with abstract formulas and equations, confusing the hell out of us. then give the most complicated example they can find from the book. pathetic.
@brendawilliams8062
Жыл бұрын
You cannot cycle it and it’s information can only go through a process of its this than it’s that.
Fast, clean, and with a good example. Quality work, you did good. Thank you.
Thanks a lot! I have a test tomorrow xx
@MichaelSambol
9 жыл бұрын
Polka dot Orchidea Glad I could help!
@miguelflor1600
Жыл бұрын
@@MichaelSambol és bueda da fixe
Really saved my day after spending hours in the text books to understand this. Thanks a lot!
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
my professor made this WAY more confusing in a 75 min lecture, you explained it perfectly in 2 minutes
I watched this during my bachelors, now I am watching it during my masters hopefully will be back during PhD
@MichaelSambol
Жыл бұрын
go get that doctorate
You are awesome. Seriously you taught a whole book chapter in just two minutes. 👍🏻
Michael, your vids are so succinct and effective.
Thanks!!! You literally saved me ... and my exam's tomorrow! You explained something in 2 minutes when in class it took like 2 hours!
Great stuff man,,, crisp and precise... never going to forget Kruskal's algo now
Your material is simply excellent! I can't wait for more!
Very succinct and to the point. Thanks for this.
Saved my life on the exam morning! Thank you so much :D
I never watched anything on this nor was taught in class so I’m just looking at this out of own interest, but that seems extremely easy. Can sort the edges, then take the minimum such that there is no cycle made. Cycle can easily be found, if you use a set for nodes that are connected to the MST being built, if both have been visited, then you don’t consider that one at all, skip. Alternatively for those into competitive programming, a min segment tree could be an interesting use case. O(e) to build, o(log e) for queries on min and updating edges you add in to be an int max length. Then again you’d have e queries at most, and each query/update takes log e time, so still e log e, but just preference and a different way to look at it.
My professor explained this for 20 minutes and couldn't make the idea clear. Thank you.
Hi I have a final exam CS 1332 tomorrow morning and your video helped me a lot. Thanks so much and go Yellow Jackets!
Concise and easy to understand, many thanks, Michael.
great video bro, you explained this so much better and in like 1/30th the time of my teacher lmao
@MichaelSambol
Ай бұрын
thanks man!
Man this video is old and I hope you see this, but it is the last I need to watch for my class. For an entire semester you managed to make my lecturer obsolete, saving me a LOT of time, and making things as clear as possible, I wish I could buy you a beer.
@MichaelSambol
3 жыл бұрын
I'll take you up on the beer, if I'm ever in your city :)
@SuperOpposum
3 жыл бұрын
@@MichaelSambol Well I got a 84 on my test, I'll buy you the entire brewery.
@miguelflor1600
Жыл бұрын
@@MichaelSambol és bueda da fixe
Thanks for helping, got a test today and explained much better than my professor. Thanks a lot :D
fuck yes, simple. Hopefully this will help on my data structures test, though usually what you study the most is what the instructor completely leaves out.
i liked the way you guys explain it, shor and clear.
Short, simple and clear. Good work !! Many thanks to you
Ok guys, it’s finals again and time to meet up with these youtubers the night before the test, to learn about a topic that we didn’t understand from professors taught weeks ago.
Simple and straight to the point. Thankyou so much!
Thank you!! Excellent explanation contrary to the million slides in my notes that are just plain confusing.
Thank you so much. This is the clearest explanation I've seen
This channel is the best. I wish I watched these in college. Please make more videos on algorithms topics!
I did not think it was possible. Nicely done
Straight forward👏🏼nice one
Thanks fam, your review and example vids are dank af
@ryandavis7506
7 жыл бұрын
haha didn't think I'd see the word 'dank' uttered in the comment section of an algorithms review video...classic
@WVZEIJL
7 жыл бұрын
Ryan Davis ayy got a 7.7 / 10 partly thanks to this guy
Short and comprehensive... Great job!!!
Generational help done by u 😭🛐
what a fantastic video. seriously this is a great explanation shrunk to a 2 min video
thank you, thank you so fucking much. You cant possibly from this planet. My fucking prof cant explain it in 2 hours and you fkin nailed it in 2 min. Glory to you sir. Mightly Michael Sambol.
amazing, just what i wanted and needed
my prof made this look like it's the hardest thing ever after talking to women. THANK YOU.
This saved me so much time. Very clear and informative video, thank you!
either this discrete mathematics text book is actively trying to confuse me to lead me to fail, or you're a Godsend...probably both haha! thank you so very much, this was the best 1.5 minutes I've experienced today!
@MichaelSambol
Жыл бұрын
Thanks for watching, Elle! The code is linked in the description if you need it.
@miguelflor1600
Жыл бұрын
@@MichaelSambolés bueda da fixe
Thanks man! Just as your video on ford-fulkersons algorithm, simple and straight forward. Cheers
11 years later, thank you very much
@MichaelSambol
2 ай бұрын
You're welcome!
Saved me so much time. Thank you for great videos.
short and sweet i like it. Keep up the good work!
this ... was ... amazingly ... made ... simple ... OMG!!!
@miguelflor1600
Жыл бұрын
ele deu gosto porque é bueda da fixe
This is amazing, love this channel! Thank you :)
u and v are vertices in the graph. {u,v} is the edge between those two vertices.
thank you bro, you are the real man
summer test tomorrow for my discrete math class, ur a hero
Short and clear review, thanks 👍
Simple and no bullshit. Love it!
Holy shit thank you I was not about to watch a 30 damn minute video on how to do this
@MichaelSambol
Жыл бұрын
short and sweet
@miguelflor1600
Жыл бұрын
@@MichaelSambolés bueda da fixe
Thanks a lot for this short explanation!
The best tutorial ever
This is great, best Math video on KZread.
This was beautifully done, thank you!
dude your saving lives here
sir thank you ! it's very clean and understandable explication !
You're amazing. Thank you !
ur the reason i might pass my ds/algo class
Excellent explanation!
excellent work, man!
bro changed my life