0:03

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.

Â 3:02

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.

Â 12:04

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.

Â 22:30

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.

Â