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.