To introduce the algorithms for minimum spanning tree, we're going tp look at a general algorithm called a greedy algorithm. It's a good example of a general principle in algorithm design that will help us, prove correctness of our algorithms. To begin we'll make some simplifying assumptions. First we assume that the edge weights are all distinct, and that the graph is connected. And this is just to simplify the presentation. As a consequence of these two exhumptions we know that the minimum spanning tree exists and is unique. Our algorithms will still work when edge winks are not distinct. And if the graph is not connected, it'll find spanning trees or components. But these two assumptions simplify the presentation. Now, to understand our algorithms we're going to start with a general operation on graph called making a cut. So a cut in a graph is a partition of its vertices into two non-empty sets, And we'll indicate that just by coloring some of the vertices grey and others white. So that's a partition of the two sets: the grey vertices and the white vertices. Every vertex is either grey or white, And there's at least one in each set. Now, given a cut, the crossing edge connects a vertex in one set with a vertex in the other. So every edge that connects a grey vertex to a white vertex is a crossing edge. So that's, a second definition. That gives us a way to talk about, inches and graphs when we compete them into a spanning tree. So an important property that is relevant to MST algorithms is that, given any cut at all, The cut defines a set of crossing edges. The minimum weight crossing edge is in the MST. Remember no two edges have the same weight so there's a single edge that has minimum weight from the edges in the edges in the cut. So in this case the thick red edge is the minimum weight, it's the shortest edge connecting a grey vertex to the white one and that, that edge has to be in the MST. That's the cut property. So here's a, just a quick proof of that property. I'll hand wave a bit through the discussions of the proof. It's a. Usually not appropriate to fully dimension proofs in the lectures. So you should look at the book and the underlined materials to be sure that you understand the proofs or, or re-read these slides. But I'll try to give all the steps. So, we're trying to prove the cut property. Giving any cut the crossing edge in many ways to MST. So let's suppose the contradiction. So suppose that we have a minimum-weight crossing edge that's not in the MST. So, in this case, that edge E, suppose it's not in the MST. So it means that some, one of the other crossing edges has to be in the MST. Otherwise the MST wouldn't be connected. Then if you add E to the MST you get a cycle. And some other edge in that cycle has to be a crossing edge. That's the way to think about it. Remember MST is a minimal way to connect the graph. And if you add an edge to a, a tree you get a cycle. And then some other edge that has to be a crossing edge. But if you remove that edge and add e then you're going to get a spanning tree. And that spanning tree is smaller than the one that you had. So, that, supposition had to be a contradiction. So, it has to be that the minimum weight crossing edge is in the MST. So that's the, cut property. So, and now given that property, we can develop what's called a greedy algorithm, Which is the easiest algorithm, we can come up with. So what we're going to do is start with, all edges colored grey. Find any cut that has no black crossing edges. The algorithm's going to color some of the edges black. And color the minimum-weight edge of that cut black, and just repeat the algorithm. Finding any cut with no black crossing edges, color the minimum-weight edge black, and keep going until you have v minus one edges that are colored back. And the claim is that that's going to compute an MST. Let's look at a demo of that, just to make sure that we follow what's going on. So we start with all edges colored gray. We're supposed to find a cut with no black crossing edges and colors minimum weight edge black. Well, that could be any cut. In this case, we'll take the cut that, has three, two, and six on one side and, one, zero, zero, one, four, five, seven on the other side. Look at all the crossing edges. Minimum white crossing edge is the one from zero to two, so the, that's the one that we'll color black. So now we have zero, two and the MST is color black. So again, any cut that doesn't have a black crossing edge, so in this case, let's do the cut that just has five on one side and all the odds on the other side. In this case, there's three crossing edges, the smallest one is five, seven, color that one black. Again, any cut that has no black crossing edges. So let's just take six the cut that has six on one side and all the others and the other. Two, six is the minimum crossing edge so six, two. And so we put that one on the MST. As we get more and more black edges it's going to be harder to find a cut with no black crossing edges. But we press on. So now let's do the cut with zero, two, four, and six on one side colored white. And one, three, five, and seven on the others. So there's a lot of crossing edges that cut. But the smallest one is the one between zero and seven, so that's the one that we color black and add to the MST. So now we have four edges, and our next cut now one and three on one side. A smallest edge in that, right, the smallest crossing edge for that cut is two, three. Now one more, now let's put one and four, now almost all the edges left are crossing edges. So one and four are one side, all the rest are in the other. And, the minimum weight crossing edge is the one from one to seven. Now notice, in this case, we got the nodes in the tree on one side of the kit, cut. And the nodes not in the tree on the other side of the cut. One of our algorithms will always have that property. So now, we add one to seven. Seven in seven to that, And now the last thing, is to. The only cut that, has no black edges is the one that puts four on one side, and all the rest on the other. And the minimum way of crossing edge for that one is, five, four. So now, we've got. eight vertices, And seven vertices in the seven edges in the MST. so we found the MST. We've got V minus one edge is color black and we found the MST. So the greedy algorithm was a very general algorithm. We're allow to find any cut at all that has no black cras crossing edges. So let's do the correctness proof. And then we'll look at some specific instances of the greedy algorithm. So. First of all since we took the minimum crossing edge of a cut always to color black any black edge is in the MST. That's the cut property. Do a cut no black crossing edges you can color black, that's in the MST. So that's first observation. Now when we have. Fewer than v minus one black edges. There has to be a cut that has no black crossing edges. That is the algorithm doesn't get stuck. And so the way to think about that is just take the verticies in one of the connected components, and make that the cut. Then there's gonna be, since that's a connected component there's gonna be no black edges in the crossing edges for, for that cut. So the algorithm doesn't get stuck. If the, if you don't have an MST yet, there's going to be some cut with no black crossing edges. And that's it. The greedy algorithm computes the MST. Any edge colored black is in the MST, And you can always add to the set of black edges. Now if you don't have v minus one once you have v minus one you've got v minus one edges that are in the MST. The MST has v minus one edges greedy algorithm computes mst. So now what we want to do is implementations of the greedy algorithm or, or specializations of it really that differ first of all in the way that they choose the cut. Which cut are we going to use? And also, the way in which they find the minimum weight edge in the cut. Again, those could both be, expensive operations. And prohibitively, prohibitively expense, expensive for huge graphs. What we're going to look at is, two classic implementations called Kruskal's Algorithm and Prim's Algorithm. Although, in both cases, we use modern data structures to make them efficient for huge graphs. And there's another interesting algorithm called Boruvka's Algorithm, that, that kind of combines the two briefly mentioned. Now before getting to those, what about removing the two simplifying assumptions? So what happens if you have, a situation where the edge weights are not all distinct? So in this, case, 1-2 and 2-4. Both have the same edge weight. Well so also do one three and three four. And so it means there's multiple MSTs. So in this case the, there's two different MSTs. So the greedy algorithm is still correct, it turns out, our correctness proof doesn't quite work, but that can be fixed with a little bit of work. So the fact is it's still correct. And if the graph is not connected, as I mentioned, then what we'll get is what's called a minimum spanning forest, which is the MST of each component. Essentially it's like independently computing the MSTs of the components. But. Basically what the greedy algorithm gives us is an easy way to prove correctness for specific algorithms. All we have to show is that they're finding a cut and taking a minimum weight edge from that cut. And then we can prove correctness of a more complicated algorithm. In general, in algorithm design this is proven to be affective in all kinds of domains. Trying to come up with a general algorithm that you can prove works efficiently and then using that to help design specific ones. The point is, ladies and gentlemen, that greed, for lack of a better word, is good. Greed is right. Greed works. Greed clarifies, cuts through and captures the essence of the evolutionary spirit. Greed in all of it's forms. Greed for life, for money, for love, knowledge, has marked the upward surge of mankind. And greed, you mark my words, will not only save Teldar Paper, But that other malfunctioning corporation called the USA. Thank you very much. . Great, great. Fly me to the moon, and let me play among the stars. .