Okay, so it's time to discuss our first 
minimum spanning tree algorithm namely 
Prim's algorithm. 
Definitely a candidate for the greatest 
hits compilation. 
And again remember even though it's 
called Prim's algorithm, it was actually 
discovered earlier by Jarnik. 
So how's it work? 
Well before showing you any pseudo code, 
let's first illustrate it on an example. 
As we go through the example, I hope that 
the similarities to Dijkstra's shortest 
path algorithm will be evident. 
I'm going to work with the same example 
graph from the previous video with four 
vertices and five edges. 
The plan is to grow a tree one edge at a 
time. 
And we're going to keep growing this tree 
like a mold. 
We're going to start from just a seed 
vertex. 
And then we're going to suck up one new 
vertex with each iteration of the 
algorithm. 
So, this is similar to Dijkstra's 
Algorithm. 
In Dijkstra's Algorithm, it was clear 
where we should grow the initial mold 
from, because we were given a source 
vertex, that they're trying to compute 
the shortest paths out of. 
We have no source vertex in the minimum 
spanning tree problem, but it turns out 
that we can just pick an arbitrary vertex 
to start. 
Doesn't matter which one, which is cool. 
So the plan is in E generation we're 
going to add one edge and span one new 
vertex adjacent to the ones we're already 
spanning. 
Now as a greedy algorithm Prim is simply 
going to select the cheapest edge that 
allows it to span one additional new 
vertex. 
Now the start of the algorithm here we're 
not really spamming anything. 
We are sort of thinking of ourselves as 
growing from and currently spanning the 
vertex in the upper right. 
So what are the edges in which we can 
span an adjacent vertex? 
Well, there is two inches. 
There is the top inch that costs one then 
we'll span an addition in the upper left 
vertex or the is the edge with cost two 
on the right. 
If we include that, we'll be able to span 
the vertex in the bottom right. 
So we're not going to be greedy, we're 
just going to choose the cheaper edge, 
the edge of cost one. 
Now, the vertices that our tree thus far 
spans are the top two vertices. 
So, in the next iteration, we want to add 
one more edge [COUGH] to span one 
additional new vertex. 
And now we see that there are three edges 
sticking out of what we're spanning thus 
far that will allow us to span a new 
edge. 
There's the edges that have cost two, 
three, and four. 
The two and the three will allow us to 
span the vertex in the bottom right. 
If we pick the four, that will allow us 
to span the vertex in the bottom left. 
Yeah, and we're going to be greedy, so of 
these three candid edges, we're going to 
pick the cheapest one which is the edge 
of cost two. 
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. 
So as usual with a greedy algorithm, this 
seems natural enough, but it's not at all 
clear that it's correct, that it always 
computes in minimum spanning tree. 
In fact, if you think about it's not even 
obvious, it actually computes a spannin 
tree at all, minimum or otherwise, but it 
is correct. 
Let's make that statement precise on the 
next slide. 
So the key claim is that Prim's Algorithm 
is correct. 
Given any connected input graph, it is 
guaranteed to output a spanning tree with 
minimum possible cost. 
So before we delve into any details, let 
me just finish this video by telling you 
about the proof plan. 
We're going to prove this theorem in two 
parts. 
First, we're going to establish that it 
outputs some spanning tree. 
Maybe, maybe not minimum. 
Even that's non trivial. 
Then we'll worry about arguing that the 
spanning tree output actually is one of 
minimum cost. 
Both parts of the proof are interesting. 
For part one to argue that we output some 
spanning tree, we're going to review some 
preliminaries about graphs and about cuts 
and about spanning trees and graphs. 
For part two to argue optimality, we're 
going to rely on a very neat property of 
spanning trees, minimum spanning trees 
called the cut property. 
I'm happy to report so that the work that 
we do here and in both parts will bear 
further fruit later we're going to reuse 
these ingredients when we prove the 
correctness of another MST algorithm 
named McCrustgrals algorithm. 
For those of you who would much rather 
talk about running time than correctness 
don't worry your time will come after we 
wrap up this correctness proof I'll 
address how do you implement prim's 
algorithm quickly in particular using 
heaps we'll get the running time down to 
the near linear bound of O of M log n.