So now the mold that we've been growing is in effect, covers all of the verticies

except for the one in the bottom left. So now in the final iteration we want to

include one more edge so that we span that final remaining vertex.

The one in the bottom left. Note that there's there was this edge of

cause three that we never added. But it got sucked up into the tree that

we grew anyways. So we're going to go ahead and ignore

that. Adding the three wouldn't allow us to

span any more vertices. In fact, it would create a loop which we

don't want. So we're going to say, okay.

We'll have the two edges that would allow us to span an extra vertex.

There's the four and there's the five. We're going to be greedy,

we're going to pick the four. And once we have the edges of the cost

one and two and three and four we have a spanning tree there's no loops there's a

path from any vertex to any other vertex along the pink edges, the cost is seven

you might recall from the previous video this is indeed the minimum cost spanning

tree of this graph. Of course, the fact that we have this

simple procedure that works correctly in this toy example, which is four vertices

and five edges, really means nothing. I mean you shouldn't draw any immediate

conclusions that this is a good algorithm in general even though that is going to

be the case. So let's next go and actually define the

algorithm generally. So if you have a general graph, what does

it mean to start somewhere and grow a mold, span one more vertex each

iteration, always proceeding greedily until you are done.

So lets spell out the pseudo code on the next slide.

So here is Prim's minimum spanning tree algorithm.

We're going to start with just two lines of initialization.

We're going to maintain a set of vertices, capital X.

This is meant to the be the vertices that we span so far.

Again, we need some seed vertex from which to start the process.

It doesn't matter where, which one we pick.

We're going to get the same tree no matter what, so just call it little s.

That's an arbitrary vertex from which we start growth.

The other thing we're maintaining is, of course, the tree.

So that's initially going to be empty. We're going to add one edge to it in each

iteration. An invarient that we are going to

maintain throughout the algorithm is that the edges that currently reside in the

set capital T span the verticies that currently reside in the set capital X.

Then we're going to have our main while loop.

this is the workhorse of the algorithm. And it's very similar to the one in

Dijkstra's algorithm. Namely, each iteration is responsible for

picking one edge crossing the current frontier.

advancing to include one new vertex. And again, it's going to be greed.

The criterion's going to be different, in fact, simpler, than with Dijkstra's

Algorithm instead of looking at links. We're just going to say, what's the

cheapest edge that allows us to span a new vertex?

So the loop's going to keep going, as long as there are vertices that we don't

yet span. And then what we do is we search to the

edges that allow us to span a new vertex. So which edges are those?

Well we want there to be one endpoint in the set X of vertices we already have our

tree spanning and we want the other end point to be non-redundant, so we want it

to be outside of X. So if we have an edge that crosses the

frontier in this sense, one endpoint in X, in endpoint outside that's how we

increase the number of spanned vertices by one in an iteration.

So if E is the cheapest edge amongst all of those that cross the front here with

one end point on either side, that's the one we're going to add to our tree so far

capital T in this iteration, it's end point that's not already in capital X,

that's going to be the very text that we add to X in this iteration.

And again the semantics of an iteration is that we're trying to increase the

number of spanned vertices while paying as little as possible, that's the sense

in which a prim's algorithm is a greedy algorithm.