0:03

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.

Â