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.