Next we'll look at another classic
algorithm for computing the MST called
Prim's algorithm.
It's also an extremely simple algorithm to
state. What we're going to do now is start
with vertex zero and we're going to grow
the tree one edge at a time, always
keeping it connected.
The way we're going to do that is add to
the tree the minimum weight edge that has
exactly one endpoint in the tree computed
so far, and we'll keep doing that until
we've grown the whole v-minus one edge
tree.
Let's look at a demo to see how that
works.
So we start with vertex zero.
And we're supposed to add them in minimum
edge that's connected to zero.
So that's zero, seven Out of all the edges
connected to zero, that's the one of
minimum weight.
So now we have one edge, two vertices on
the tree.
And so now we want to add the min weight
edge that connects to the tree.
In this case, that's seven, one out of all
the edges that connect to the tree, one,
seven is the shortest one, so that's the
one that we add.
So now we have two edges on the tree.
Continuing now, the min weight edge that
connects to the tree is zero, two so, we
add that one.
So, now we have three edges, four vertices
on the tree.
The closest edge, the closest vertex to
the tree or the smallest edge coming out
of the tree is two, three so we add that
one.
So now we have three more vertices to go,
and you can see that the next one that's
going to come is five.
That's closer, to the three than four or
six.
So we do that, add five, now there's two
more and so, out of all those edges, the
closest one to the tree is 45.
It's a little shorter than four, seven and
zero, four.
So that's the one that gets added and then
finally six gets added to the tree by the
surest edge that connects it to the tree,
which is six, two.
So start with vertex zero, add an edge at
a time to the tree, it's the shortest edge
that goes from, a tree vertex to a
non-tree vertex, that's Prim's algorithm.
Now let's look at Prim's algorithm running
on, on the same huge graph that we ran for
Kruskal's.
This is also a fascinating dynamic
process.
Usually, the new edge, is, close to, the
last edge added.
But every once in a while, it gets stuck.
And so, jumps to a new place, to add
edges, to the MST.
This algorithm's a little bit easier to
follow.
But it's a very interesting dynamic
process.
You can see that it, when it's easy, it
just sticks where it was.
And when it runs into some long edges, it
gets stuck and tries somewhere else.
Always adding to the tree, the shortest
edge that connects a non-tree vertex to a
tree vertex.
And you can see the last few things to be
added where the vertices in the upper left
corner.
So that's a visualization of Prinz
algorithm.
Completely different character, but comes
out to the same tree as Kruskal's
algorithm as long as the edge weights are
distinct.
So we need to prove Prim's algorithm
correct and this one has been rediscovered
a, a few times depending on how you cast
the data structure for implementing
finding the minimum.
But the basic algorithm has been known
since at least 1930 and it's proof that it
computes the MST again comes because it's
a special case of the greedy MST
algorithm.
So the, let's suppose that E is the
min-win weight edge connecting the vertex
on the tree to a vertex not on the tree.
Well, you just, you take, as your cut, the
tree vertices.
There's no black crossing edge from the
tree vertices to non tree vertex.
That's a definition that's not on the
tree.
And there's no crossing edge of low
weight, cuz that's the minimum one.
That we picked by design.
So it's a special case of the Greedy
algorithm where you take, as the cut, the
set of vertices currently on the tree.
That's Prim's algorithm.
Now how are we going to implement Prim's
algorithm?
How are we going to find the minimum
weight edge with exactly one point and T?
Well, one thing that we could do is just
try all the edges.
And, maybe some early implementations that
would do that.
But what we're going to do is use a modern
data structure of priority q.
So we're going to keep the, edges, on a
priority queue.
But, have exactly one end point in T.
And then we can just, pick out the minimum
weight one.
That's a so called, lazy implementation of
Prim's algorithm.
We'll look at another one, called the
eager implementation afterwards.
So, what we need to do is find the minimum
weight edge with exactly one endpoint in
the tree.
So, the solution is to make a priority cue
of the edges that have at least one end
point in the tree.
And then we, using as priority, the key is
the edge and the priority is the weight of
the edge.
And so, we're going to. Use delete min to
find the next edge to add to the tree.
And then we have to update the priority
queue.
When we consider that edge, now there's
going to be some edges on the priority
queue that are obsolete, and we've already
found better ways to connect them, so
we'll just disregard an edge that has both
endpoints in the tree, we've already found
a way to connect them and we don't need
that edge for the minimum spanning frame.
That's why it's called a lazy
implementation.
We allow stuff to be on the priority queue
that we know is obsolete.
And then when we pull it off the queue we
test whether it belongs in the tree or
not.
But then the key step in the algorithm is
to assume, is to, what do you do when you
get a new vertex for the minimum pan in
tree and a new edge.
So that means that one of the vertices is
on the tree, let's say that's v and the
other one is not on the tree.
That means W.
And so what we want to do is add W to the
tree but then we also want to add to the
priority Q, any edge that's incident to W.
So that's got the possibility, as long as
this other end point is not in the tree.
So those edges have the possibility of
being minimum spanning tree edges in the
future unless some better way to connect
their incident vertex to the tree is found
before they come off the queue.
And that's the algorithm.
A lazy solution of Primm's algorithm.
So lets take a demo of that.
So what we're going to do is start with a
vertex and really grow the tree.
Add to T the mid-weight edge with exactly
one end-point entry in the tree.
That's Primm's algorithm.
But now we're going to show the data
structure, the priority Q, that allows us
to do this.
By keeping all the edges that we know
about that connect, that possibly could be
that edge on priority Q.
So let's look at what happens, for our
sample graph.
So we start at vertex zero,
That's fine.
Now, we're going to add that, to the tree,
vertex zero to the tree, and we're going
to put in the priority queue, all the
edges that are, incident to zero.
And just for, the demo, we'll just show
the, edges sorted by weight, with the
understanding that we have a heaped data
structure or something under there, to
give us the smallest one.
But, for the demo, it's easiest to see,
them sorted by weight.
Okay so then to greenly grow the tree we
have to pick 0,7 off the priority queue.
But and so we'll show that one on the MST.
And then the vertex that's not, on the
tree at that point is seven, so we're
going to add seven to the tree.
So first we add zero, seven to be an MST
edge, and then we add to the priority
queue all the edges that are incident to
seven, that. All the edges into, incident
to seven that point to places, the
vertices that are not on the tree that are
connected to vertices that are not on the
tree.
So we don't put zero, seven back on'cause
zero is already on the tree.
So we put all those on a priority queue.
And, again, keep them sorted by weight.
So, now let's continue.
So smallest thing is one, seven.
That's the smallest edge, to a from a tree
edge to a non-tree edge.
And so that's, delete 1,7 from the
priority queue and add it to the MSTs, so
we do that.
And now that takes us to one and so now we
have to add to the priority queue, all the
edges that, connect, one to non-tree
edges.
So that's what the asterisks are, are the
new, new edges on the priority queue.
And again, we keep ''em sorted by weight.
So now what we want on the priority queue
is a subset of the, you wanna be sure that
every edge that connects a tree edge to a
non-tree edge is on the priority queue.
We might have a few others as well, and
we'll see that in, in a second.
So now 0,2's the smallest so we take 0,2
and add it to the MST.
So notice now that once we add two to the
MST, this edge between one and two becomes
obsolete.
It's never going to be added to the MST.
At the time that we put one on, we thought
maybe that was a good way to get to two.
But now we know there's a better way to
get to two.
So that edge becomes obsolete.
And the lazy implementation just leaves
that edge on the priority Q.
So let's now continue, so, we added, two
to the, 0-2 to the MST.
And we have to add, everybody infinite the
two, that, is not on the tree, to the
priority queue.
So, in this case, it's 2-3 and 6-2.
We don't have to add 1-2 and 2-7, 'cause
they go to three edges.
We don't add'em back on.
Okay, so now the smallest is two, three.
So take that, add it to the MST.
And add all the edges incident to three to
non-tree vertices, in this case it's just
three, six.
And that's a long one.
So now the next edge for the MST is five,
seven.
Take that off the priority queue, put it
on the MST.
And so and now all peak, all edges
incident to five that go to non tree
vertices.
It says just five, four and that one.
So now the next edge that would come off
the priority que is one, three but, that's
an obsolete edge.
We already have one, three connected in
the MST because we were lazy and left that
in the priority que.
So now we just pull it off and, and
discard it, because it connects through
three vertices.
Same with 1,5.
We already have a better way to connect
them.
2,7 connects through three vertices.
And finally we get to four, five.
4,5 now gets deleted.
And from the priority queue, and add it to
the MST.
Everybody connected to four, that's just
six, and that's a long one, goes on.
Now we have some obsolete edges we'll get
to that one too.
And then four, seven is obsolete, and
zero, four is obsolete.
And finally, the last edge to get added to
the MST is six, two.
And after deleting 6-2 from the priority
queue and adding the MST we have, computed
the MST.
We have V minus one edges on V vertices,
and that's, implementation of the lazy
version of Prim's algorithm.
And it's just a version of Prim's
algorithm we showed was the underlying
data structure, the priority queue, that
ensures that we always get the shortest
edge connecting a tree vertex to a
non-tree vertex.
So let's look at the code for Prim's
algorithm.
Again, the data structures that we build
up in part one of this course, give us a
very compact implementation of this MST
algorithm.
So we're going to need three instance
variables.
One is a existence array.
A vertex indexed array of bullions, that
for each vertex.
Will tell us whether or not it's on the
MST.
Then we have the, list of edges on the
MST, that, is going to be, returned to the
client after the MST is computed, to, for
iterable.
And then we we'll have the priority queue
of edges that, connect, tree vertices with
non-tree vertices.
The super-set of the edges that connect
tree vertices and non-tree vertices.
So.
Given a graph we'll build a priority
queue.
We'll initialize all the data structures.
And then we'll visit, and we'll show what
the routine does.
That's the one that processes each vertex
when it gets added to, to the tree.
We'll look at that in the next slide.
So the main loop is, while the priority q
is not empty, we pull off the minimum edge
from the priority q.
We get it's constituent vertices, if their
both marked then we just ignore it.
They're already on the MST.
Otherwise, we put the edge on the MST.
And which ever vertex was not on the tree,
we visit and put on the tree.
And the visit routine is the one that puts
the vertex on the tree and puts all of its
indecent edges on the priority Q.
So to visit a vertex we set its entry,
corresponding entry in the marked array to
be true, so it's, added to the tree.
And then for, every edge, that's adjacent
to that, we're going to, if it's, other
edge is not marked, we're going to put it
on the priority Q.
So if it's an edge that goes from a tree
vertex to a non-tree vertex, we put it on
the priority Q.
And then, we have the, client query method
to, get the MST, once the, MST is built.
Again, the data structures that we've used
give a very compact and complete
implementation of Prim's, Prim's
algorithm.
What's the running time of the algorithm?
Well, it's correct cuz it implements
Prim's algorithm as we've showed us in the
sense of a greedy algorithm.
And it's easy to see that the running time
is always going to be proportional to E
log E in the worst case.
And that's because you could put all the
edges on priority Q and. So, every edge
would, might, would have to come off the
priority cue, so that's e times, and then
the cost would be proportional to e for,
inserting and deleting, every edge off the
priority cue.
So, E log e is sorry, is a fine running
time.
The space, extra space proportional to e
is you know, might be considered annoying,
or inelegant, or inefficient so there's a
more efficient version of Prim's algorithm
where we clear off that dead weight on the
priority queue.
And that's the eager implementation of
Prim's algorithm that we'll look at next.
In practice, the lazy implementation works
pretty well, but the eager implementation
is all.
So a very elegant and efficient algorithm,
and it's worth learning both.
So for the eager solution, what we're
going to do is.
The priority Q is going to have vertices.
And it's going to have, at most, one entry
per vertex.
And so those are the vertices that are not
on the tree but are connected by an edge
to the tree.
And the priority of a given vertex is
going to be the weight of the shortest
edge connecting that vertex to the tree.
So if we look at this little example here
Where we've build the tree for zero, seven
and one then the Black.
Entries in this are the ones, the edges
that are on the MST.
So that's zero, seven and one, seven and
the red ones are the ones that are on the
priority Q because they're connected by an
edge to some vertex that's on the tree.
And for each one of them, there's a
particular edge that connects, that's
shortest, that connects that vertex to the
tree.
So that's the key for the priority Q.
So that's what we're, that's what we're
going to want for at any time during the
execution of the algorithm.
We're going to want the vertices that are
connected to the tree by one vertex.
And, and we're going to know the shortest
edge connecting that vertex to the tree.
So then, the algorithm is again, delete
the minimum vertex.
And it's got an associated edge that
connects it to the tree, and we put that
one on the tree.
And then we have to update the priority
queue.
So why do we have to update the priority
queue.
So we have.
This vertex that's not on the tree, we
consider all of the edges that are
incident to that vertex.
If they point to a tree vertex then we're
going to ignore it.
That's no problem.
If it's not already on the priority Q,
we're going to put that new vertex on the
priority Q.
And then other thing is, if the vertex is
on the priority Q and we just found a
shorter way to get to it, then we're going
to have to decrease the priority of that
vertex.
So, let's look at how that works in a
demo.
So, again, it's just an implementation of
Prim's algorithm.
It's just how to we get the min weight
edge that connects to the tree?
And this is a, a more efficient way to do
it.
So, again, we start out with our graph,
started zero, and, let's get going.
So, now, the priority QS vertices, and so
there's four vertices that are just one
edge away from the tree, and, we keep'em
on the priority queue, in order of their
distance to the tree.
So, and we also keep the edge.
Two vertice, vertex index arrays.
One is the edge that takes us to the tree,
and the other is the length of that edge.
And again we'll keep sorted on the
priority queue just to make the demo
easier to follow.
So the next vertex to go on the tree is
seven.
The next edge to get added to the tree is
edge two of seven.
And then we go from there.
So that's the smallest one, we take that
for the tree and now we have to update the
priority q.
So, how do we update the priority q?
Well we have to look at, everybody
incident the seventh, and so, let's look
at, so, for example, 7-2.
We don't need to put 7-2 in the priority
queue, since we already have a better way
to connect two to the tree, thats 2-0.
So we don't have to change anything.
Same with 7-4.
And about 7-5, and 7-1.
One and five are not on the priority
queue.
So, we have to put them on the priority
queue.
And, then save the edges in length that,
get them, to seven which would get them to
the tree.
So now, on our priority queue, we have our
current tree.
And we have all vertices that were within
one edge of the tree.
And the edge that gets'em to the tree, and
their length.
So, we're ready for another step of the
algorithm.
So now seventeen is the smallest thing in
the priority queue.
And so we put that on the MST.
And now we look at everybody connected to
one.
And again, one seven we [inaudible],
because it's on the tree.
One five we don't need cuz we have a
shorter way to get to the tree.
One two we don't need cuz we have a
shorter way, to get, two to the tree, but
we haven't seen three yet so we add vertex
three to the priority cue and say we get
to the tree by one, one three, distance
point two nine.
Every, all the vertices within one edge of
the tree and the edge and length of the
shortest edge that gets.
To the tree from that vertex, that's what
we're maintaining at every step.
Okay so next vertex to come to the tree is
two and so we put that on the tree and now
we look at everybody that connected to
two, so now we have our first example of
decrease key but let's, let's check them
all.
So two, zero.
Two, seven, and two, one, take us to
vertices that are already on the tree.
So it's two, three and two, six.
So what we need to do for three, we had
thought that the best way to get to three
from the tree from three was to go to one.
And adding this new edge two means we now
know a better way to get from three to the
tree.
So we have to update the priority.
Update the edge two, in the priority we
have to decrease the key of the priority.
So that's an operation that we're going to
need from our priority Q.
And it's something that has to be factored
into our priority Q implementation.
And the same thing for six.
We thought we had a good way to get to the
tree from zero but two brings six closer
to the tree so we have to update that
information.
And say now the best way to get from six
to the three is 6,2 and that it's length.
We have to decrease the key.
And this definitely.
Involves summary shuffling in the priority
queue and our implementation is going to
take that into account.
So, with those changes now, we have the
following situation.
And, we've got, four edges on the tree.
Three edges on the tree.
Now we're going to add the fourth, which
is 2-3.
That's the smallest thing on the priority
queue.
So we add, two, three to the MST.
And now we have to go to the, things
connected to three, And, well, there's
nothing to add, since we already have a
better way to six.
So next one that gets added is 5-7.
And check, so, edges from five, seven.
So.
We from five, We're going to decrease the
key of four from.38 to.5.'Cause the best
way to get from four to the tree is no
longer 4,0, it's 4,5.
So again, decrease the key and discard the
longer edge to the tree.
And in fact, that's the next edge that we
pick.
And we don't bother putting forth six on,
'cause we already have a better way to get
from six to the tree.
And then the last edge that we had was
6,2.
Again, it's the easy version of Prim's
algorithm is an implementation that always
connects to the tree, the vertex that's
closest to the tree.
But we use a more efficient data structure
to do it.
That can only have one, at most one entry
per vertex, as opposed to one entry per
edge.
So that's the eager version of the Prim's
algorithm.
Okay rather than focus on the code for the
eager version.
Which is quite similar to the code for the
lazy version.
We're going to talk briefly about the Key
data structure that we need to implement
this.
And it's the implementation of the
priority Q that allows us to decrease
keys.
And so, this is a advanced version of the
priority Q that we talked about in part
one of the course.
But it's necessary for algorithms like
this.
So what we're going to do, The problem is.
We have keys that the priority queue
algorithm doesn't really, Needs to know
when we change values of keys, and so we
have to do that through the API.
And so what we're going to do is allow the
client to change the key by specifying the
index and the, and the new key.
And then the implementation will take care
of changing the value and updating its
data structures to reflect the changed
values.
You can't have the client changing values
without informing the implementation.
The priority queue implementation.
That's the basic challenge for this data
structure.
So since we are working with vertex
indexed arrays and graphs.
And, the priority queue implementation
might do the same.
We'll just associate an index.
Kind of pass that idea onto the priority,
queue.
To make it allow it to implement these
operations officially.
So the constructor gets to know how many
indices or how many keys there are going
to be at most ever in the priority Q.
And so it can make use of that to
implement efficient data structures for
the operations.
And so insert just associates a key with a
given index.
Decrease key allows to decrease the keys
associated with a given index we can
check.
Whether that's a bug should be Mth K.
Is an index on the priority Q.
We can remove a minimal key and give it's
associated index.
Check whether it's empty and give its
size.
Now it's pretty much a topic for part one
of the course, but we'll give just one
slide here to show how these indeces kind
of help things go around.
We're basically going to use the same
code, the heap based implementation of min
PQ. But we'll keep parallel arrays that
allows us to access quickly all the
information that we need.
So things on the queue are accessed by
index, and so we'll keep the values in
keys, so that's where the keys are.
So PQ of I will give the index of the key
that's in heap position I and QPI is the
heap position of the key with index I.
So that is the information that you need
when the client changes a value, you.
Need to get to the, you have to actually
first of all change the value but then you
may need to adjust the heap to, To reflect
the changed value.
So instead of a swim with an index, we use
the, we get the heat position of the given
index, and so forth.
So if you look in the book, you'll see the
code for index priority Q, and it's
definitely a confusing topic for a
lecture, but it's important to realize
that it's possible to implement this
decreased key operation in logarithmic
time without ever having to search
through.
Everything for anything, using the idea of
indexing.
So with that change, We get, for all the
operations, we get time proportional to,
log v.
And, what do we have to do for, the eager
version of Prim's Algorithm?
We, we have to, might have to insert every
vertex once, and delete min, every vertex
one.
And we might do as many as E decrease key
operations.
So that gives us a total running time of E
log V.
But the main thing is that the amount of
space for the priority q, is.
Only V not E.
And that can make a difference for a huge
graph.
So there are modifications that you can
make to this.
That give a more efficient running time.
For example, one easy thing to do is to
use since the operation we're performing
most often is the decreased key.
If we use a multi-way heap, like say a
four way heap, or in general a D way heap.
Then that reduces the cost of that
operation.
And it's.
Slightly increases the cost for insert and
delete min but there's not many of those,
so we can get the running time to log base
e over v of v.
And that, if you do the math for various
types of graphs, that's, that's going to
be faster.
And in fact a data structure called the
Fibonacci heap was invented in the'80s
that actually gets the running time down
to e plus v log b, although that data
structure's too.
Complimented to actually, too complicated
to actually use in practice.
If you have a, a dense graph.
Then you wouldn't even use a heap.
You'd just use an array and find the
minimum by going through, everything.
Since every vertex has, lots of connected
vertices.
So we didn't consider that one.
Because the huge graphs that we find in
practice are, are sparse.
And a binary heap is going to be much
faster.
And if you really have a
performance-critical situation, it's
worthwhile to do a four way heap.
That's the, basic bottom line in the
running time of Prim's algorithm.