Edit Style Paragraph 00:00 So now let's learn Kruskal's algorithm, which is actually just another way to find the minimum spanning tree of a connected graph. So maybe if Prim's algorithm was too confusing for you, you might prefer Kruskal's algorithm. And actually, in my opinion, conceptually, it's a much easier algorithm to understand. Now, coding it up might be a bit more difficult, and that's because it actually uses the union find data structure. 00:27 So if you can just use like a built in union find data structure, it's pretty easy to code this algorithm up. But if you can't, you'll have to implement your own union find, which is not super complicated, as we learned earlier. But it does take quite a bit extra code to do that. The idea is similar to Prim's algorithm. We want to take minimum edges. We want to be greedy. 00:48 We want to add the edges with the smallest weight because we want our minimum spanning tree to have the minimum cost of connecting all these nodes together. 00:56 but instead of prim's algorithm where we start at a single node and then just add adjacent nodes to our frontier and then you know after we've added one of those adjacent nodes then we have like a larger frontier then we have more nodes to choose from and then you know we choose the minimum of the you know adjacent neighbors instead of doing that kruskles actually skips that all together we just take all possible edges and then start taking the minimum of those edges and then add that to our minimum spanning tree. 01:27 So the idea would be that among all these edges, pick the one with the smallest weight. In this case, it's one. So we add this to our minimum spanning tree. So now we have these two nodes as a part of our minimum spanning tree. Now we don't actually mark these as visited. Kruskal's handles it a bit differently. This is where it can get a bit more complicated actually. 01:51 because now we're gonna add the next edge with the smallest cost. It's gonna be two. So we already had these two as a part of our graph. Now we're adding this edge. And this edge actually also includes a node that we already added before. So how do we know we're not introducing a cycle? Well, that's where union find comes in actually. We initially start with this graph and we have five individual nodes, right? 02:19 We have five individual components of this graph. As we add edges, for example, when we add this edge, we essentially union these two together. These are now a part of a single connected component, but we also have three individual nodes remaining. Then when we add this edge, we're essentially connecting this portion to this node. Since these were not previously connected to each other, we know for sure 02:48 we're not introducing a cycle, right? We're not introducing a redundant edge. But now as we continue, we've added these two cycles. We're going to take now among the remaining edges, the one with the minimum cost. In this case, it's this edge. So this time we have, you know, this component over here and a couple of edges connecting these nodes together. But now we just added this edge, which connects these two nodes together. 03:15 So we have two connected components, but that's perfectly fine. We don't have a cycle, but we know we want all the nodes to be connected to each other without forming a cycle. So now we have five nodes, so we know for sure we're going to need four edges. So now at this point, we can actually choose any of these three edges and all of them will form a minimum spanning tree. 03:37 So if we add this edge, then this becomes our minimum spanning tree. If we add this edge, then this 03:44 becomes our minimum spanning tree. And if we add this guy, then this becomes our minimum spanning tree. Notice how none of them have a cycle. So that would be our result. We would end up choosing one of these three and we would get our result. But the reason Kruskal's algorithm works is because we make sure that we don't introduce an edge that creates a cycle. 04:04 Now, this example didn't really illustrate that super well, but let's say I change this one to a four. Well, I'm gonna change this three to an eight, let's say. So now when we try to build a minimum spanning tree, we're gonna choose the edge with the smallest weight. It's this one, so we connect these two together. Now among these four, we have a tie. So I'm just gonna arbitrarily choose this one. 04:25 So when we introduce this edge, we do not create a cycle because we're connecting two different components together. Now let's add another one. Let's arbitrarily choose this one. That's okay because we had one component over here and we had another component over here. Our union find is gonna tell us 04:41 that we are allowed to union these two together because they're not already a part of the same connected component. So that's what we're going to do we're going to union them together. Then among these two, let's say we pick this edge. Well, the problem is that these two nodes here are already a part of the same connected component. 05:00 So by adding another edge here, we know for sure we're creating a cycle because they're already a part of the same component. That means there's already a path from c to D. So by adding another edge here, we're creating another path from C to D. Now there's two paths here. And since we know this graph is undirected, that means that we have a cycle. 05:25 So since our union find would tell us that this edge is redundant, that these are already connected, we would choose not to add this edge. So we would remove it from consideration without adding it to our minimum spanning tree. Then among the remaining nodes we would choose 05:41 This one, because it has the smallest cost. And again, we would find that these two nodes are actually a part of the same connected component. So if we add this node, we're gonna create a cycle. So we're not gonna add this node. Once again, we're gonna skip it. Well, this edge. Once again, we're gonna skip this edge. Now among these two remaining, we could add either of these two nodes actually would create a tree. 06:05 Then all these would be connected if we add this edge. Also, we could add this edge and again, all of these would be connected. But we want to minimize the cost, so we're going to choose the one with the smallest weight, and this is the one that we're going to choose. Every time we introduce an edge, we want to make sure we're connecting two nodes together that previously were not connected. 06:28 That's going to get us to forming a tree. By choosing the one with the minimum cost, we're going to ensure that we create the minimum spanning tree. 06:35 so kruskal's algorithm is just another greedy algorithm, just like dixtra's algorithm and prim's algorithm. So the code here is quite a bit shorter actually. And the reason is because the union find data structure, I'm not showing the code for that, but if you want to see the entire code for that, I will have it below. You can also, of course, go to the union find lesson to understand the implementation of the union find data structure. 07:01 So given a list of edges, We're not actually going to need to build an adjacency list in this case, because for any given node, we don't really care what its neighbors are. We don't care at all. We just care about the entire list of edges. And using those edges, we will make sure that we don't create a cycle by using union find. 07:19 So in this case, our heap actually is going to be initialized with every single edge in the input. We're also given n, which is going to be the total number of nodes. And we're going to be told that each node is labeled from 1 through n. 07:33 now going through the list of edges, each edge is going to have two nodes connecting them together. We don't really care about the source and the destination because we know each edge is undirected anyway. So node 1 node 2 and it's going to have a weight. We know we care about the weight the most when we're pushing to the min heap. That's the value that's going to be used to decide how to pop first. 07:53 And the nodes also matter. But in this case, actually, the order that we put the nodes does not matter at all because when we add them to the union find, it doesn't really matter what order we union them together. So we're going to initialize our union find data structure, giving it n for the number of nodes that we're initializing it with. We're going to have an empty array for our minimum spanning tree. 08:14 And this time, we're going to continue the algorithm while the length of the minimum spanning tree is less than n minus 1 because we know we have n nodes in the graph. 08:23 We know we're just going to need n minus one edges to form the minimum spanning tree. As long as every time we add an edge, we're not introducing a cycle. So we're going to pop from the min heap the weight node one and node two. We don't really care about the weight. It was just used to pop the edge with the smallest weight, but we're not going to need that weight again. 08:42 We're going to take these two nodes, try to union them together. But if not, if we can't union them together, we're simply going to skip them. 08:51 this edge we're going to continue to the next iteration of the wild loop but if we can union them together then we're going to take that edge we're defining the edge as being node 1 to node 2 and taking that edge and adding it to the result the minimum spanning tree and then once we've done that n minus 1 times we're going to simply return 09:11 what the minimum spanning tree is. Now, what do you think the time complexity of Kruskal's algorithm is? Well, it's pretty similar to Dijkstra's algorithm and pretty similar to Prim's algorithm because we are pushing and popping from the min heap. The main difference here is that we also have union find. As we pop from the heap, we're also unioning two nodes together. 09:31 Now, the time complexity for popping from the heap is gonna be log n, or rather log e, where e is min. 09:39 the number of edges in the entire graph that's the worst case and we know e can be reduced to v squared and we know that two can go over here so really the time complexity to pop is log v and actually unioning two nodes depending on how you implement the union find with path compression and union by rank it could also be a log e or maybe it could even be a constant time operation so 10:05 This union find actually doesn't really matter. It doesn't really affect the time complexity because the heap pop operation is roughly the same time complexity anyway. So no matter how efficient we make this, it doesn't matter. This is going to be the bottleneck. So the overall time complexity sense, we may push and pop from the min heap a total of E times for the total number of edges. 10:26 And we know pushing and popping each time is going to be roughly log V. So this is the overall time complexity. The overall memory complexity is going to be big O of E. E, because we have to take every single edge and add it to the min heap, so that's where the memory complexity comes from. 10:41 So even though a lot of these ideas can definitely be difficult to wrap your head around, I hope you're starting to see the similarities. Most graph algorithms have a lot of similarity between them, and that's definitely true for the minimum spanning tree algorithms, definitely true for the shortest path algorithms as well. 10:59 So now whenever you need to find a minimum spanning tree, you have two ways of doing it. You can use Prim's algorithm or you can use Kruskal's algorithm. You can do whichever one you prefer. I sort of prefer Prim's algorithm because it's similar to Dijkstra's algorithm, which is more common. Kruskal's though is pretty dang easy, especially if you don't have to implement union find from scratch.