Kruskal's Algorithm

Easy to Advanced Data Structures Union find/Disjoint set
6 minutes
Share the link to this page
Copied
  Completed
You need to have access to the item to view this lesson.
This is a free item
$0.00
د.إ0.00
Kz0.00
ARS$0.00
A$0.00
৳0.00
Лв0.00
Bs0.00
B$0.00
P0.00
CA$0.00
CHF 0.00
CLP$0.00
CN¥0.00
COP$0.00
₡0.00
Kč0.00
DKK kr0.00
RD$0.00
DA0.00
E£0.00
ብር0.00
€0.00
FJ$0.00
£0.00
Q0.00
GY$0.00
HK$0.00
L0.00
Ft0.00
₪0.00
₹0.00
ISK kr0.00
¥0.00
KSh0.00
₩0.00
DH0.00
L0.00
ден0.00
MOP$0.00
MX$0.00
RM0.00
N$0.00
₦0.00
C$0.00
NOK kr0.00
रु0.00
NZ$0.00
S/0.00
K0.00
₱0.00
₨0.00
zł0.00
₲0.00
L0.00
QR0.00
SAR0.00
SEK kr0.00
S$0.00
฿0.00
₺0.00
$U0.00
R0.00
ZK0.00
Already have an account? Log In

Transcript

Okay, let's talk about a really neat application of the Union find, which is Crew Skills minimum spanning tree algorithm. So you might be asking yourself what is a minimum spanning tree. So if we're given some graph with some vertices and some edges, the minimum spanning tree is a subset of the edges which connects to all the vertices and does so at a minimal cost. So, if this is our graph, with some edges and some vertices, then a possible minimum spanning tree is the following and has edge weight 14 or total edge weight 14. Note that the minimum spanning tree is not necessarily unique. So if there is another minimum spanning tree, it will also have a total weight of 14.

So how does it work? So We can break it up into three steps essentially. So the first step is easy. Just take our edges and sort them by ascending edge, edge weight. Next thing we want to do is we want to walk through the sort of edges and compare the two nodes that the edge belongs to. And if the nodes already belong to the same group, then we want to ignore it because it'll create a cycle in our minimum spanning tree which we don't want.

Otherwise, we want to unify the, the two groups those nodes belong to and keep going. And we'll keep doing this process until either we run out of edges or all the vertices have been unified into one big group. And you'll soon see what I mean by a group, which is when our union find data structure is going to come into play. So if this is our graph, then to Run Chris was algorithm on it first, let's scale the edges and sort them. So on the left side you see I have all the edges and their edge weights sorted in ascending order. So next we're gonna start processing the edges one at a time.

Started starting with the top, so I should J. So I farted the edge it Jane Finch. And you can see that it connects nodes, i and j. i and j currently don't belong to any group. So I'm going to unify them together into group orange. Next is edge he so he don't belong to any group. So I'm going to unify them together into group purple.

Next is CGI. So I belong subgroup orange, but See doesn't have a group yet. So seeking go into group orange. Alright, e to AF, f doesn't belong to a group. So F can go to group purple. Next, H and G, need neither age nor g belong to a group.

So I'm going to say you guys belong to the red group. And next we have DDB. They also don't belong to a group. So give them their own group, let's say group green. All right, and now, I believe this is when things start getting interesting. Now we're trying to connect C to J.

But notice that scene j era both belong to group orange, so we don't want to include that edge because it's going to create a cycle so ignore it. And to check that they belong to the same group. We would use the find operation in our union To check what group they belong to. So this one, the unifying really comes into play. Next is edge, did he. So note that he belongs group purple, and D belongs to group green.

So now we want to merge them together because they don't belong to the same group. So either the purple groups want to come to the green group, the green groups and the purple group, it doesn't really matter. So now we would merge them and this one the union operation in our union find becomes useful. It allows us to merge groups have colors together very efficiently, and that's the important note. Next edge would be d h, h belongs to group red, and D to purple. So merge the groups together.

Let's say they become good purple. Next up, we want to Add edge, add, but add already belong to the same group. So that would create a cycle. So we don't want to include that edge. So skip next want include edge BTC BTC belong to different groups. So merge the two groups into one larger group.

So we have found the minimum spanning tree using crystals, minimum spanning tree algorithm. Pretty neat, right? So the underlying data structure which allows us to do this is the unified it allows us to merge groups of colors together efficiently but also to find out which groups nodes belong to so that we don't create a cycle. So so that's crystals algorithm. It's super simple. Given that you know how the union find works.

So I'm going to go into some detail in next video, explaining how the Find and And the union operations work internally and how we can actually implement it in some useful way. All right, I'll see you guys then. But thank you so much for watching and I will catch you next time.

Sign Up

Share

Share with friends, get 20% off
Invite your friends to LearnDesk learning marketplace. For each purchase they make, you get 20% off (upto $10) on your next purchase.