Kruskal's algorithm in 2 minutes 

Are you from outer space? My lecturer couldn't explain this in 2 hours and you did in 2 mins. Thanks a lot.

you explained something in 2 minutes what my prof did in two lessons.

“If you can't explain it to a six year old, you don't understand it yourself.”

Fucking legend mate!

this is why I don't watch lecture recording

tfw: this is actually really simple but your professor unnecessarily complicated it

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.

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

Seems simple enough.. but not so simple for coding :P

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.

Thank you so much, we were given incomprehensible pseudo-code and confusing notation. For this to seem so simple after a

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).

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.

Very nice video. Straight to the point and quick.

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.

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.

I watched this during my bachelors, now I am watching it during my masters hopefully will be back during PhD

You say that we must not connect 2 nodes that are already in the same tree but you then add AC into the MSP. But both of these are already in a tree, yet we cannot select BE

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.

How do you tell if two edges are in the same tree without it being very time complex? \

great video bro, you explained this so much better and in like 1/30th the time of my teacher lmao

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 !

Why tf did i choose cs 😭

Thanks a lot! I have a test tomorrow xx

This was way easier than my prof's explanation. Thank you so much!

u and v are vertices in the graph. {u,v} is the edge between those two vertices.

Great video. Thanks so much for making it!

核心思想就是如果俩点都在一个系统里了，就没必要介绍他俩了

Even in 2021, you are still relevant. Thank you for your service

4 hours of discrete mathematics lectures and seminaries ... compressed in 2 minutes. you sir, are a life saver

You sound like Ryan from Supermega lol

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!

dude how many graphs did you draw lol?

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 :)

my prof made this look like it's the hardest thing ever after talking to women. THANK YOU.

i dont get why you pick A-C at 0:57,but later you dont pick B-E

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.

Still relevant in 2021. Thank you!

Dude you saved my ass from a F

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.

شكرًا :)

Thank you so much.

Epic Explaination lol

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.

Saved my life on the exam morning! Thank you so much :D

You are a life saver! Also you need a donate button!

At what course are you studying this :) I'm in 1st of informatic engineering :)

You are a LIFE SAVIOR. Thanks!

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.

Actually time complexity is theta(Elog(E)) if you choose merge sort, you can have O(Elog(E)) instead if you choose heap sort. Right?

wait why did you add A->C, but not B->E, if the reason you didnt add B->E was because they were already visited? Is it because of the no-cycle rule or the "cant add two nodes previously visited rule"? Thanks for the video though :D

the nodes A and C are in the the tree but are still added why are they added

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.

saving my final, i love you

trop bien chacal jai dead ca

I feel like this video should be titled something like "Intuitive Understanding of Kruskal's Algorithm".

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!

Why is (A,C) chosen since it makes 2 nodes on the same tree?

hi.. could you please help me with travelling sales person problem with branch and bound technique? Need help in emergency!!

Perfect tutorial I have ever seen. Thanks, I got it in just 2 minutes!

The explanation is very intuitive and concise, thank you so much.

sir thank you ! it's very clean and understandable explication !

If you choose to connect CE then AB, then BE, then AD, then DF, then FG you'd have another MST.

Why is the Subscribers has stopped to 95k , it should be atleast 7-8M

this guy explained this god damn thing more clearer in 2 minutes, than my professor who spent a whole week. but, college is worth it right?

long shot but is it possible to have connect B and E vertices while not connecting A and C vertices. I believe the reason for not connecting B and E vertices is because it would have formed a cycle.

i was going to write krusty crab and kruskal's algorithm appeared, now im watching this

You have done it wrong, minimum spanning weight is 24, you obtain 25

this ... was ... amazingly ... made ... simple ... OMG!!!

Not all heroes wear capes

Most university lecturers waste too much time, I've wasted mine too

On 0:48, couldn't he have chosen BE instead of AC?

Very succinct and to the point. Thanks for this.

What was the point of adding AC if A and C were already discovered?

Is it proven that this is the optimal solution? Curious because it might not be optimal to pick the smallest weighted edge all the time

I wish you had used a color other than red to highlight the added edges, as I'm red-green color blind.

what is the difference of Prims and Kruskal?

Straight forward👏🏼nice one

the algorithm is ez to understand, but coding it is a problem

then why did u chose A,C a and c were also two nodes that were already in your graph.

How can I thank you so simple like the video?

Very nice! Thanks from Munich.

čau

Thanks - From university of Wolverhampton^^^

hold on how do i know which one is the smallest edge? what makes you label the numbers there in that order?

if nodes a and c were already in the tree why did you add the edge between them to the tree? right after you make the point thatb and e are already in the tree so you dont add that edge. Im confused :(

Could anyone explain to me why B and E edge is not chosen?

W channel. Love the videos

i need unique kruskal method

You're amazing. Thank you !

Why did you add A , C as both have been already visited.

It is important to note that there can be many MSTs in the same graph

So when you choose one of the 3-value edges you say, that it doesn't matter which edge I'm going to choose, but what would it be, if i had choosen the BE Edge first? I'd get to a different result or wouldn't i? How would i note a correction in the MST? That would be very helpful, thank you!

precise and concise

At 0:58 why added edge AC? Vertices A and C are already visited and you gave the same reason to exclude the edge BE. Answer: It is because vertices B,E belong to the same disjoint set and their edge (BE) is excluded. Source: Minimum Spanning Tree #1: Kruskal Algorithm

you saved my ass one more time

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!

Goddamn. And to think i spent a week in school on this

Generational help done by u 😭🛐

i have a question you choose same graph in your video of prims algo , their total weight of graph was 24, but in this total weight of graph after finding minimum spanning tree is 25, shouldn't it must be same