Union Find Kruskal's Algorithm

Okay, let's talk about a really neat application of the union find which is Kru School's 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 um with some edges and some vertices then a possible minimum spanning tree is the following and has edge weight 14 well 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 all our edges and sort them by ascending edge edge weight. Next thing we want to do is we want to walk through the sorted edges and compare the two nodes that the edge uh 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 uh the the two groups those nodes belong to and keep going. And we 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's 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 going to start processing the edges one at a time. Uh started starting with the top. So I to J. So I've harded the edge I to J in orange. And you can see that it connects nodes uh I and J. I and J currently don't belong to any group. So I'm going to unify them together into group uh orange. Next is edge 8 to E. So A to E don't belong to any group. So I'm going to unify them together into group purple. Next is uh C to I. So I belongs to group uh orange, but C doesn't have a group yet. So C can go into group orange. All right. Uh E to F. F doesn't belong to a group. So F can go to group purple. Next, H and G. Ne neither H nor G belong to a group. So, I'm going to say you guys belong to the red group. Next, we have D2B. Uh they also don't belong to a group. So, give them their own group. Let's say uh group green. All right. And now, I believe this is when things start to get interesting. Now we're trying to connect C to J. But notice that C and J already 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 find to check what group they belong to. So this is when the union find really comes into play. Uh next is edge D to E. So note that E belongs to 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 group is going to become the green group or the green group's going to become the purple group. It doesn't really matter. So now we would merge them. And this is when the union operation in our union find becomes useful. allows us to merge groups of colors together very efficiently and that's the important note. Uh next edge would be uh D to H. H belongs to group red and um D to purple. So merge the groups together. Let's say they both become group purple. Uh next up we want to add edge A to D. But A to D already belong to the same group. So that would create a cycle. So we don't want to include that edge. So skip it. Uh next we want to include edge B to C. Uh B to C belong to different groups. Uh so merge the two groups into one larger group. So we have found the minimum spanning tree using Cruc's minimum spanning tree algorithm. Pretty neat, right? So the underlying data structure which allows us to do this is the union find. It allows us to merge groups of colors together efficiently but also to find out which groups uh nodes belong to uh so that we don't create a cycle. So so that's Chris's algorithm. It's super simple u 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 the union operations work internally and how we can actually implement it in some useful way. All right, I will see you guys then but thank you so much for watching and I will catch you next time.