So, in these next few videos, we're going to continue our discussion of the minimum cost spanning tree problem. And I'm going to focus on a second good algorithm, good greedy algorithm for the problem, namely Kruskal's algorithm. Now, we already have an excellent algorithm for computing the minimum cost spanning tree in Prim's algorithm. So you might wonder, you know, why bother spending the time learning a second one? Well, let me give you three reasons. So the first reason is this is just a, it's a cool algorithm. It's definitely a candidate for the greatest hits. It's something I think you should know. It's competitive with Prim's algorithm both in theory and in practice. So it's another great greedy solution for the minimum cost spanning problem. The second reason is it'll give us an opportunity to learn a new data structure, one we haven't discussed yet in this course. It's called the union-find data structure. So, in exactly the same way or in a similar way to how we used heaps to get a super fast implementation of Prim's algorithm. We use a unionfind data structure to get a super fast implementation of Kruskal's algorithm. So that'll be a fun topic just in its own right. The third reason is, is there's some very cool connections between Kruskal's algorithm and certain types of clustering algorithms. So that's a nice application that we'll spend some time talking about. I'll discuss how natural greedy algorithms in a clustering context are best understood as a variance of Kruskal's minimum spanning tree algorithm. So let me just briefly review some of the things I expect you to remember about the minimum cost spanning tree problem. So the input of course is an undirected graph, G and each edge has a cost. And what we're trying to output, the responsibility of the algorithm is a spanning tree. That is a subgraph which has no cycles and is connected. There's a path between each pairs of vertices and amongst all potentially exponential many spanning trees, the algorithm is supposed to output the one with the smallest cost, smallest sum of edge costs. So let me reiterate the, the standing assumptions that we've got through the minimum spanning tree lectures. So first of all, in assuming if the graph is connected, that's obviously necessary for it to have any spanning trees. that said, Kruskal's algorithm actually extends in a really, just easy, elegant way to the case where G is disconnected. But I'm not going to talk about that here. secondly, remember, we're going to assume that all of the edge costs are distincts, that is there are no ties. Now don't worry, Kruskal's algorithm is just as correct. If there are ties amongst the edge costs. I'm just not going to give you a proof that covers that case, but don't worry, a proof does, indeed exist. Finally, of the various machinery that we developed to prove the correctness of Prim's algorithm perhaps the most important and most subtle point was what's called the cut property. So this is a condition which guarantees you're not making a mistake in a greedy algorithm. It guarantees that a given edge is indeed in the minimum spanning tree. And remember, the cut property says, if you have an edge of a graph and you could find just a single cut for which this edge is the cheapest one crossing it. Okay? So, the edge E crosses is cut and every other edge that crosses it is more expensive. That certifies the presence of this edge in the minimum spanning tree, guarantees that it's a safe edge to include. So we'll definitely be using that again in Kruskal's algorithm when we prove it's correct. So as with Prim's algorithm, before I hit you with the pseudocode, let me just show you how the algorithm works in an example. I think you'll find it very natural. So let's look at the following graph with five vertices. So the graph has seven edges and I've annotated them with their edge costs in blue. So here's the big difference in philosophy between Prim's algorithm and Kruskal's algorithm. In Prim's algorithm, you insisted on growing like a mold from a starting point, always maintaining connectivity, and spanning one new vertex in each iteration. Kruskal's going to just throw out the desire to have a connected subgraph at each step of the iteration. Kruskal's algorithm will be totally content to grow a tree in parallel with lots of simultaneous little pieces, only having them coalesce at the very end of the algorithm. So in Prim's algorithm, while we were only allowed to pick the cheapest edge subject to this constraint of spanning some new vertex. In Kruskal's algorithm we're just going to pick the cheapest edge that we haven't looked at yet. Now, there is an issue, of course, we want to construct a spanning tree at the end. So, we certainly don't want to create any cycles, so we'll skip over edges that will create cycles. But other than that constraint, we'll just look at the cheapest edge next in Kruskal's algorithm and pick it if there is no cycles. So let's look at this five vertex example. Again, there is no starting point. We're just going to look at the cheapest edge overall. So that's obviously this unit cost edge and we're going to include that in our tree. Right? Why not? Why not pick the cheapest edge? It's a greedy algorithm. So what do we do next? Well, now we have this edge of cost two, that looks good, so let's go ahead and pick that one. Cool. Notice these two edges are totally disjoint. Kay.' So we are not maintaining a connectivity of our subgraph at each iteration of Kruskal's algorithm. Now, it just so happens that when we look at the next edge, the edge of cost 3, we will fuse together the two disjoint pieces that we had previously. Now, we happen to have one connected piece. Now, here's where it gets interesting. When we look at the next edge, the edge of cost 4, we notice that we're not allowed to pick the edge of cost 4. Why? Well, that would create a triangle with the edges of costs 2 and 3, and that of course is a no-no. We want to span the tree at the end of the day, so we can't have any cycles. So we skip over the 4 because we have no choice, we can't pick it, we move on to the 5 and the 5 is fine. So when we pick the edge of cost 5, there's no cycles, we go ahead and include it. And now we have a spanning tree and we stop or if you prefer, you could think of it that we do, we do consider the edge of cost 6. That would create a triangle with the edges of costs 3 and 5, so we skip the 6. And then, for completeness, we think about considering the 7, but that would form a triangle with the edges of costs 1 and 5, so we skip that. So after this single scan through the edges in assorted order, we find ourselves with these four pink edges. In this case, it's a spanning tree and as we'll see, not just in this graph but in every graph it's actually the minimum cost spanning tree. So, with the intuition hopefully solidly in place, I don't think the following pseudocode will surprise you. We want to get away with a single scan through the edges in short order. So, obviously in the preprocessing step, we want to take the unsorted array of edges and sort them by edge cost. To keep the notation and the pseudocode simple, let me just, for the purposes of the algorithm, description only, rename the edges 1, 2, 3, 4, all the way up to m conforming to this sorted order, right? So, the algorithm's just going to scan through the edges in this newly found sorted order. So we're going to call the tree in progress capital T, like we did in Prim's algorithm. And now, we're just going to zip through the edges once in sorted order. And we take an edge, unless it's obviously a bad idea. And here a bad idea means it creates a cycle, that's a no-no, but as long as there's no cycle, we go ahead and include the edge. And that's it, after you finish up the for loop you just return the tree capital T. It's easy to imagine various optimizations that you could do. So for example, once you've added enough edges to have a spanning tree. So n - 1 edges, where n is the number of vertices, you can get ahead, go ahead and abort this for loop and terminate the algorithm. But let's just keep things simple and analyze this three line version of Kruskal's algorithm in this lecture. So just like in our discussion of Primm's algorithm, what I want to do is first just focus on why is Kruskal's algorithm correct? Why does it output a spanning tree at all? And then, the spanning tree that it outputs? Why on earth should it have the minimum cost amongst all spanning trees? That's when we're, once we're convinced of the correctness, we'll move on to a naive running time implementation and then finally, a fast implementation using suitable data structures.
