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.