Union Find Kruskal's Algorithm

Рет қаралды 198,473

7 жыл бұрын

Introduction to Kruskal's Algorithm
Related Videos:
Union find intro: • Union Find Introduction
Union find kruskal's algorithm: • Union Find Kruskal's A...
Union find union and find: • Union Find - Union and...
Union find path compression: • Union Find Path Compre...
Union find code: • Union Find Code
Data Structures Source Code:
github.com/williamfiset/algor...
====================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix ===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Пікірлер: 70

@andreas9109 5 жыл бұрын

4:25. It does matter! The smaller group becomes part of the greater group, otherwise the worst case runtime would be different.

@TheDemeaN 4 жыл бұрын

yas it does matter but I think he was saying in the context of find the mst in the graph, like imagine an exam exercise where you need to draw the mst

@JanacMeena 3 жыл бұрын

Merging a smaller group into a larger group would require fewer operations, but it does not affect the worst-case runtime. Please let me know if I'm wrong!

@lordquaggan 2 жыл бұрын

@@JanacMeena It actually does! Weighted union keeps tree depth below log(n), even in the worst case (can prove by induction), so find is O(log(n)), while without weighted union, tree depth can be n in the worst case, leading to O(n) find. Applied to Kruskal's algorithm, this is the difference between an overall O(mlog(n)) and O(mn) complexity.

@SAJID-zs2gf 10 ай бұрын

@@lordquaggan during each find operation you can update the parent of children and attach children directly to it's top-most parent (root node), then in that case tree-depth won't reach O(n), since at every call to find(), the children node will be attached to root node of the whole group.

@madanrajvenkatesan518 4 жыл бұрын

Such a neat and crisp explanation. People like you are making our lives simpler. Thanks a bunch !!! Keep it up.

@chepaiytrath 3 жыл бұрын

I saw your Prim's explanation using PriorityQueue first. Kruskal's using PriorityQueue and Union Find was a piece of cake thence. Your explanations are great and so is your code. Thanks a lot

@adityabhashkar3405 7 жыл бұрын

I've been trying to understand it for a long time. finally understood. thanks a lot!

@WilliamFiset-videos 7 жыл бұрын

That's really encouraging to hear! :)

@Megan-gl7pi 3 жыл бұрын

The color grouping is really intuitive. Thank you for the helpful video.

@jhonJ1245 4 жыл бұрын

Great video! Finally I understood this algorithm. I had been trying to understand it for days until I watched your video

@priscilapadilla357 2 жыл бұрын

This was absolutely freaking great. I love this stuff, u explained it so well. Thank you for reminding me why I love what I do. Keep up the great work!

@mrallenchuang 4 жыл бұрын

Your channel is so underrated. Love it!

@jagritbhupal5836 4 жыл бұрын

You have really worked hard in designing these colourful ppts/video. Thank you very much.

@JasonMelton1 6 жыл бұрын

Great illustration! This is a great series!

@iamsanin 4 жыл бұрын

Your explanation made it super simple... great work

@avocados3500 7 жыл бұрын

You made my life so much easier!

@dochell1781 6 жыл бұрын

Sehr gut erklärt. Vielen Dank :)

@guilucasds 3 жыл бұрын

This is amazing! Thank you so much for that, really!

@asafsh2306 4 жыл бұрын

Fantastic simulation my friend - keep up

@iwannarigana2258 6 жыл бұрын

Thank you!!!!!By far the best explanation!!!

@solidwaterslayer 4 жыл бұрын

i love u u explained it better than my textbook and professor regarding applications of mfset so I understand disjoint set better!

@MykolaDolgalov 4 жыл бұрын

Thank you, this is very helpful!

@aleksajanjatovic5596 4 жыл бұрын

Great job, keep it up!

@mariyambajwa9162 4 жыл бұрын

Excellent explaination! :)

@dinhnhobao 3 жыл бұрын

This is brilliant, thank you!

@juggles5474 Жыл бұрын

You rock dude, thanks for the video

@jayaprakashhasthi5775 3 жыл бұрын

greatexplanation ,you made it easy

@ayeyo4081 Жыл бұрын

very adaptive to my brain. thanks !

@prrrrrratatata 7 жыл бұрын

Well presented.

@jabir5768 2 жыл бұрын

I swear you are the king of graph theory

@picnicbros 11 ай бұрын

Basically, sort the edge then run Union Find

@nabidulalam6956 3 жыл бұрын

nicely explained. thanks.

@ankitchoudhary197 2 жыл бұрын

Thanks a lot William 😁😁

@TViener 7 жыл бұрын

Just found your channel while studying for my algorithms exam. Cannot thank you enough for making these great videos! You are f@#$!ing awesome!

@WilliamFiset-videos 7 жыл бұрын

GL on your exam!

@arjundosajh 2 жыл бұрын

nice explanation, thanks!

@YT.Nikolay Жыл бұрын

Thanks for the video, love your channel! Why did you stop after the pair "B to C"? how do I know when to stop iterating over the list on left?

@bharathateja2797 5 жыл бұрын

nice explanation thanks

@saidathanikhil.k6415 Жыл бұрын

Great explanation

@x3non500 3 жыл бұрын

Very interesting, thanks ^^

@nelsonthekinger 6 ай бұрын

This Algorithm is crazy!! I find beautiful how people come with these solutions. This is a beautiful application of Data Structures to simplify hard problems to solve. Just waw! Oh and Thanks William for bringing the quality content as usual!

@chaitanyak.n.4768 4 ай бұрын

Its just greedy search.

@AndrewBradTanner 5 жыл бұрын

Great vid

@tungtruong5904 3 жыл бұрын

I am your fan, bro!

@sallaklamhayyen9876 Ай бұрын

thank you so much

@williamhuang6200 3 жыл бұрын

how do you assign the edge weights?

@dimitrijs.869 6 жыл бұрын

very good

@nikhilrajput5030 4 жыл бұрын

Is this algorithm work when graph is directed?

@prakhargupta3283 Жыл бұрын

Can you please help me understand how are giving weight to a junction.

@matheuscosta5330 2 жыл бұрын

mind blowing

@user-ws4sk2dy1p 3 жыл бұрын

hello，Willliam can you teach me how to do the ppt, I am very interested

@ramennudeln247 Жыл бұрын

Why B to C instead of G to I or H to C is it because of node size?

@kanishk1010 5 жыл бұрын

Great illustration. Just wanted to add that union-find is an algorithm and not a data structure. Graph is a data structure.

@riteshrastogi5388 4 жыл бұрын

No its not. Read the first line ( written in black color ) of this article : cp-algorithms.com/data_structures/disjoint_set_union.html

@supportitservices6349 Жыл бұрын

Thanks

@alexvakalis9553 2 жыл бұрын

i don't understand the logic behind each number being assigned to which path. Any kind of help is aprecciated.

@FrazerKirkman 10 ай бұрын

at 5:20 you say we've found the minimum spanning tree, but how did you know that they were all connected at the point? Does Kruskals algorithm keep track of group size at each root node?

@kylewilliams9429 9 ай бұрын

The would all have the same 'root' parent. That's how you know the algorithm is complete. When every vertice has the same parent (belongs to the same 'group')

@gradientO 6 ай бұрын

You can keep track of group count. At the start, each node is a group, so it'll be the node count. Decrease the count on union. Stop immediately when the group size is one instead of going through remaining edges (which won't be added anyway)

@mantistoboggan537 6 жыл бұрын

I'm still not sure where "size" comes into play

@WilliamFiset-videos 6 жыл бұрын

Whether you merge the smaller group into the larger group or vice versa doesn't matter. It's just a good heuristic to use for efficiency of the Union find if you merge the smaller group into the larger one.

@huseyinari8654 2 жыл бұрын

ehrenmann

@hendrikombach7285 4 жыл бұрын

are the edge weights arbitrarily assigned?

@WilliamFiset-videos 4 жыл бұрын

A weighted graph will come with predetermined edge weights.

@akshatbhutra7278 4 жыл бұрын

done

@ujjvalpatel5353 6 жыл бұрын

!!!!!!!!!! WAIT , The title of your video is very misleading . It should say something like "Application of Union Find data structure (Kruskal's Algorithm)" . Cause when you say adding "C and J" will create a cycle ,that is where we need to know how union Find Algo works . else video was awesome

@williamvanderscheer4327 5 жыл бұрын

I know this is obviously very late, but for others reading this, just in case... It has nothing to do with the union find algorithm, but with Kruskal's algorithm, which tries to find a minimum spanning tree. A minimum spanning tree is the minimum set of weighted edges needed to connect all nodes. If we select edges that form cycles, then we have by default not found a minimum spanning tree. It doesn't even have anything to do with a cycle itself, it's simply because since that node was already "spanned" before (aka already in the group) we did not have to actually use that edge to visit it, and we needlessly incurred the cost by travelling over that vertex, which violates the invariant of the minimum spanning tree algorithm. A scenario that happens to be equivalent to creating cycles. (because we are reaching a node in the group, from a node that is also in that group => cycle)