Transcript
The following content is provided under a Creative Common License. Your support will help MIT Open Courseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT Open Courseware at ocw.mmit.edu. All right, let's get started. Today we have another cool graph algorithm or problem. Actually, we'll have two algorithms. Problem is called minimum spanning tree. You can probably guess from the title what it's trying to do. We'll see two algorithms for doing it. Both of them are in the category of greedy algorithms, which is something we've seen a couple of times already in 6046.
Uh starting with lecture one. This is the definition of greedy algorithm from lecture one roughly. Uh the idea is to always make greedy choices. meaning the choice is locally best for right now. It seems like a good thing to do. Uh but maybe in the future it will screw you over and if you have a correct greedy algorithm, you prove that it won't screw you over. So it's sort of like Cookie Monster here. Always locally seems like a good idea to eat another cookie, but maybe it'll bite you in the future. So, uh, today we will embrace our inner cookie monster and, uh, eat as many eat the largest cookie first would be the standard algorithm for cookie monster.
Um, I don't know if you learned that in Sesame Street, but um, all right. So, uh, what's the problem? Minimum spanning tree. Can anyone tell me what a tree is formally? Not the outside thing, but in graphland. A cyclic graph. Close. connected a cyclic graph. Good. That's important. This is 6042 stuff. Okay. So, uh how about a spanning tree? Sorry. contains all the contains all the vertices. Yeah. So let me go over here. Spanning means it contains all the vertices. So uh implicit here I guess is subtree or subgraph. You're given a graph. You want a spanning tree of that graph uh is going to be a tree that lives inside the graph.
So we're going to take some of the edges of G, make a tree out of them, make a connected asyclic graph, and that tree should hit all the vertices in G. So this is going to be subset of the edges or subgraph. uh those edges should form a tree and uh I'll say hit all vertices of G. Okay, if I just said uh they should form a tree, then I could say, well, take no edges and here's a a tree with one vertex. That's not very interesting. You want a vert, you want basically the vertex set of the tree to be the same as the vertex set of the graph. That's the spanning property. But you still want it to be a tree.
So you want it to be connected and you want it to be a cyclic. Uh now if G is disconnected, this is impossible. Uh and for that you could define a spanning forest to be like a maximal thing like this. But we'll focus on the case here G is connected. That's the interesting case. And so we can get a spanning tree. All right. So what is this minimum spanning tree problem? Uh minimum spanning tree, we're given a weighted graph. Just like last time with shortest paths, we have an edge weight function W giving me a real number. Let's say for every edge and we want to find a spanning tree of minimum total weight.
So I'm going to define the weight of a tree t to be uh the sum over all edges in t because I'm viewing a spanning tree as a set of edges of the weight of that edge. Okay, so pretty much what you would expect minimum weight spanning tree uh it's a relatively simple problem but it's not so easy to find an algorithm. uh you need to prove a lot to make sure that you really uh find the right tree. Uh I guess the the really naive algorithm here would be to try all spanning trees. Uh compute the weight of each spanning tree and return the minimum. That seems reasonable. That's correct. Uh but it's bad because H n to the 4th.
That would be nice. Uh it's larger than that. Maybe not so obvious. Uh but it can be exponential. Uh here's a graph where the number of spanning trees is exponential. This is a complete bipartite graph uh with two vertices on one side and n vertices on the other. And so you can let's say we put these two edges into the spanning tree. And now uh for each of these vertices we can choose whether it connects to the left vertex or the right vertex. It can only do one but it can do either one independently. So maybe this guy chooses the left one. This one chooses the right one. This one chooses the left one and so on.
If I have n vertices down here, I have two to the n different spanning trees. So there can be an exponential number. So that algorithm is not so good exponential bad polomial good. So today we're going to get a polomial algorithm. In fact we will get an almost linear time algorithm uh as fast as Dyster's algorithm. But uh we can't use Dyster's algorithm. There's no shortest paths here. But one of the algorithms will actually look pretty similar. Uh two lectures ago, the dynamic programming lecture, we saw example where we tried to do greedy and it gave the wrong answer and so we fell back on dynamic programming.
Today we're going to try to do dynamic programming. It's going to fail and we're going to fall back on greedy. So it's like the reverse. But the way it's going to fail is we're going to get exponential time initially and then greedy will let us get polomial time. This is actually a bit unusual. I would say more typically dynamic programming can solve anything but you know with n to the seven running time something slow and then you apply greedy and you get down to like n or n log n running time. So that's more common but today we're going to go from exponential down to polinomial and that's pretty nice.
Um, cool. So, let me tell you a little bit about greedy algorithm theory, so to speak. This is from the textbook. Uh if your problem can be solved by a greedy algorithm, usually you can prove two properties about that algorithm. One of them is called optimal substructure and the other is called the greedy choice property. Um, optimal substructure is a very uh should be a familiar idea because it's essentially anap encapsulation of dynamic programming. Uh, Greedy algorithms are in some sense a special form of dynamic programming. Uh so this is saying something like if you can solve sub problems optimally smaller sub problems or whatever then you can solve your original problem and this may happen recursively whatever that's essentially what makes a recurrence work for dynamic programming and with dynamic programming we uh for this to be possible we need to guess some feature of the solution.
Uh for example in minimum spanning tree maybe you guess one of the edges that's in the right answer. Uh and then once you do that you can reduce it to some other sub problems and if you can solve those sub problems you combine them get an optimal solution to your original thing. So this is a familiar property. I don't usually think of it this way for dynamic programming but that is essentially what we're doing. uh via guessing. But with greedy algorithms, we're not going to guess. We're just going to be greedy. Eat the largest cookie. So that's the greedy greedy choice property. This says that eating the largest cookie is actually a good thing to do.
If we keep making locally optimal choices, we end up with a globally optimal solution. No tummy ache. This is something you wouldn't expect to be true in general, but it's going to be true for minimum spanning tree and it's true for a handful of other problems. You'll see a bunch more in recitation tomorrow. Uh so first thing I'm going to this is sort of general theory but I'm actually going to have a theorem like this for minimum spanning tree and a theorem like this for minimum spanning tree. That's this is the prototype but most of today is all about minimum spanning tree. And for minimum spanning tree, neither of these is very obvious.
Uh so I'm just going to show you these theorems. They're fairly easy to prove in fact. Uh but finding them is probably the tricky part. Actually, I guess optimal substructure is probably the least intuitive uh or the least obvious greedy choice. You're probably already thinking what a good greedy choice is. Minimum weight edge seems like a good starting point uh which we will get to. But uh there's even a stronger version of that which we will prove. And first optimal substructure. So here I'm going to think like a dynamic program. Let's suppose that we know an edge that's in our solution. Suppose we know an edge that lives in a minimum spanning tree.
We could guess that. We're not going to, but we could. Um either way, let's just suppose that an edge E uh I should mention uh I guess I didn't say this graph is undirected. uh minimum spanning tree doesn't quite make sense with directed graphs. There are other versions of the problem but here graph is undirected. Uh so probably I should write this as a unordered set UV and there are possibly many minimum spanning trees. Uh there could be many solutions with the same weight. For example, if all of these edges have weight one, all of these trees are actually minimum. If all the edges have weight one, every spanning tree is minimum because every spanning tree has exactly n minus one edges.
So, uh, but let's suppose we know an edge that's guaranteed to be in some minimum spanning tree, at least one. Uh, what I would like to do is take this. So, let me draw a picture. Um, we have a graph. We've identified some edge in the graph E that lives in some minimum spanning tree. I'm going to draw some kind of tree structure here. Okay, that's the wiggly lines are the tree. Uh there's some other edges in here which I don't want to draw too many of them because it's ugly. Those are other edges in the graph. Who knows where they are? It could be all sorts of things. Okay. But I've highlighted uh the graph in a particular way.
There's because it's uh it's the minimum spanning tree is a tree. If I delete E from the tree, then I get two components, right? Every edge I remove, I'm I'm minimally connected. So if I delete an edge, I disconnect into two parts. So I've drawn that as the left circle and the right circle. This just general way to think about a tree. Now there are other unused edges in this picture. Who knows where they live? Okay. What I would like to do is somehow simplify this graph and get a smaller problem. Say a graph with fewer edges. Uh any suggestions on how to do that? I don't actually know where all these white edges are, but what I'd like to do is I'm supposing I know where E is, and that's an edge in my minimum spanning tree.
So, how could I get rid of it? Yeah, the minimum weight. I'd like to divide and conquer. Maybe find the minimum weight over here, minimum weight over here. Of course, I don't know which nodes are on what side. So, that's a little trickier. Uh, but what do I do about E itself? Let's start with that. Yeah, remove it. You could remove it. It's a good idea. Doesn't work, but worth a Frisbeeian nonetheless. Uh, if I delete this edge, one problem is maybe none of these red edges exist and then my graph is disconnected. Well, maybe that's actually a good case. Uh, that would probably be a good case. Then I know how to divide and conquer.
I just look at the connected components. In general, if I delete the edge, uh, and I have these red edges, then I maybe find a minimum spanning tree on what remains. Uh, maybe I'll end up including one of these edges. Maybe this edge ends up in the spanning tree and then I can't put E in. So, it's a little awkward. Yeah. Merge the two nodes into one. Yes. Purple frisbee. Impressive. Uh this is what we call contracting the edge. Uh it just means merge the end points. Merge U and V. So I will draw a new version of the graph. So this was U and V before. I'll put the label inside. And now we have a new vertex here which is uh UV or you can think of it as the set UV.
We won't really need to keep track of names. uh and where whatever edges you had over here uh you're going to have over here. Okay, just collapse U and V. The edge E disappears. Uh and one other thing can happen. Let me go over here. We could end up with duplicate edges by this process. So for example, suppose we have U and V and they have a common neighbor. Might have many common neighbors, who knows? And some other edges, uncommon neighbors. Uh when I merge, I'd like to just have a single edge to that vertex and a single edge to that vertex. And what I'm going to do is if I have some weights on these edges, let's say A and B and C and D.
Uh I'm just going to take the minimum because what I'm about to do is compute a minimum spanning tree in this graph. And if I take the minimum spanning tree here and I had multiple edges, one weight A, one weight B, do you think I would choose the larger weight edge? It does. They're exactly the same edge, but one is higher weight. There's no point in keeping the higher weight one. So, I'm just going to throw away the higher weight one. Take the min. So, this is a particular form of edge contraction in graphs. uh and I claim it's a good thing to do in the sense that if I can find a minimum spanning tree in this new graph, this is usually called uh G slash E slash instead of negative uh to remove E, I'm contracting E.
So this is G slash E, this is G. If I can find a minimum minimum spanning tree in G slash E, I claim I can find one in the original graph G just by adding the edge E. Okay, so I'm going to say um if t prime is a minimum spanning tree of g/ e, then t prime union e is a minimum spanning tree of g. So overall you can think of this as a recurrence in a dynamic program. And let me write down that dynamic program. It won't be a very good dynamic program but it's a starting point. This is conceptually what we want to do. Uh we're trying to guess an edge E. that's in a minimum spanning tree. Uh then we're going to contract that edge.
Uh then we're going to recurse find the minimum spanning tree on what remains. And then uh we find minimum spanning tree. Then we want to deontract the edge. Put it back. Put the graph back the way it was. And then add E to the minimum spanning tree. And what this lema tells us is that this is a correct algorithm. If you're lucky, and we're going to force liness by trying all edges, but if we start with an edge that is guaranteed to be in some minimum spanning tree, call it a safe edge, uh, and we contract and we find a minimum spanning tree on what remains, then we can put E back in at the end and we'll get a minimum spanning tree of the original graph.
So, this gives us correctness of this algorithm. Now, this algorithm is bad again from a complexity standpoint. uh the running time is going to be exponential. The number of subpros we might have to consider here is all subsets of edges. There's no particular way uh because at every step we're guessing an arbitrary edge in the graph. Uh there's no structure like we can't say well it's the first k edges or some substring of edges. It's just going to be some subset of edges. There's exponentially many subsets 2 to the e. So this is exponential. But uh we're going to make it polomial by removing the guessing.
This is actually a really good prototype for a greedy algorithm. If instead of guessing trying all edges, if we could find a good edge to choose that's guaranteed to be in a minimum spanning tree, then we could actually follow this procedure. And this would be like a an iterative algorithm. you you guess you you don't guess you correctly choose a good you take the biggest cookie uh you contract it and then you repeat that process over and over that would be a prototype for a greedy algorithm and that's what's going to work there's different ways to choose this greedy edge and we're going to get two different algorithms accordingly uh but that's where we're going first I should prove this this claim because you know where did edge contraction come from why does it work uh there's a it's not too hard to prove.
Let's do it question. No. All right. Uh should be able to do this without looking. Um so proof of optimal substructure. So we're given a lot. We're told that E belongs to a minimum spanning tree. Let's give that spanning tree a name. Uh say uh we have a minimum spanning tree star which contains E. So we're assuming that exists. Then we contract E and then we're given T prime which is a minimum spanning tree of G SE and then we want to analyze this thing. So I want to claim that this thing is a minimum spanning tree. In other words, that the weight of that spanning tree uh is equal to the weight of this spanning tree because this one is minimum.
This is a minimum spanning tree of G. And this is also supposed to be a minimum spanning tree of G. Okay, sounds easy, right? Um I'm going to cheat. Sorry. Uh, I see. Right. Duh. Uh, easy once you know how. So, what we're going to do is think about contracting E. Okay, we already know we're supposed to be thinking about contracting E in the graph. Let's look at how it changes that given minimum spanning tree. So, we have T star minimum spanning tree of the whole graph. And then I'm going to contract E. Uh what I mean is if that edge happens to be in the spanning tree. Well, uh it is actually we assume that E is in there.
So I'm basically removing I'm just deleting that edge. Maybe I should call it minus E. uh then that should be a spanning tree of G slash E. So when I contract the edge in the graph, if I throw away the edge from this spanning tree, I should still have a spanning tree. Now I don't know whether it's minimum. Probably it is, but uh we won't prove that right now. I claim it's still a spanning tree. Uh what would that take? It still hits all the vertices because uh if I remove the edge things would not be connected together. But uh this edge was in the spanning tree and then I fuse those two vertices together.
So uh whatever spanning I mean whatever was connected before is still connected. Contraction generally preserves connectivity. Uh if these things were already connected directly by an edge when I contract I still have a connected structure. So I'm still hitting all the vertices. Um, and also the number of edges is still exactly right. Before I had n minus one edges. Afterwards, I'll still have n minus one edges because I removed one edge and I removed one vertex in terms of the count. So that proves that it's still a spanning tree uh using properties of trees. Uh, cool. So that means uh the minimum spanning tree this thing t prime the minimum spanning tree of g/e has a smaller weight than this one because this is a spanning tree the minimum is smaller than all spanning trees.
So we know the weight of t prime is less than or equal to the weight of t star minus e. Uh, cool. And now we want to know about this thing. The weight of T prime plus E. Well, that's just the weight of T prime plus the weight of E because the weight of a tree is just the sum of the weights of the edges. So, this is less than or equal to W of T star minus E plus E. uh which is just the weight of t star. Right? So we proved that the weight of our proposed spanning tree is less than or equal to the weight of the minimum spanning tree in g and therefore t prime union e actually is a minimum spanning tree.
Okay, this is really easy. actually implies that all these inequalities have to be equalities because we started with something minimum. Clear? That's the easy easier half. The more interesting property is going to be this greedy choice property. Uh this is sort of where the action is for greedy algorithms. And this is usually the heart of proving greedy algorithms are correct. We don't yet have a greedy algorithm, but we're thinking about it. uh we need some way to intelligently choose an edge E. And I'm going to give you a whole bunch of ways to intelligently choose an edge E. Uh little So, here's a really powerful lema.
We're going to make it even stronger in a moment. Um, so I'm going to introduce the notion of a cut. Uh, it's going to be a similar picture to what I had before. I'm going to look at some set of vertices. S here is a subset of the vertices. And that leaves in the graph everything else. This would be V minus S. Okay. So there's some vertices over here. Uh some vertices over here. There's some edges that are purely inside one side of the cut. And then what I'm interested in are the edges that cross the cut. Okay? Whatever they look like. these edges. If if an edge has one vertex in V and one vertex not in V, I call that edge a crossing edge.
Okay. Uh so let's uh suppose that E is a uh least weight edge crossing the cut. So let's say uh let me be specific. If E is uh UV uh then I want one of the end points let's say U to be in S and I want the other one to be not in S. So it's in capital V minus S. Okay, that would be a crossing edge and among all the crossing edges I want to take one of of minimum weight. There might be many but pick any one then I claim that edge is in a minimum spanning tree. This is our golden ticket, right? If we can guarantee an edge is in the minimum spanning tree, then we plug that in here. Instead of guessing, we'll just take that edge.
We know it's in a minimum spanning tree. And then we'll contract it and repeat this process. So uh the tricky part I mean it is true that the minimum weight edge is in a minimum spanning tree. I'll give you give that away but the question is what do you do then uh we want to keep being I guess you contract and repeat but that will be Kuscal's algorithm but uh this is in some sense a more general tool that will let us identify edges that are guaranteed to be in the minimum spanning tree even after we've already identified some edges as being in the minimum spanning tree. So, it's a little more powerful.
Let's prove this this claim. This is where things get particularly cool. And this is where we're going to use something called a cut and paste argument. And if you are ever trying to prove a greedy algorithm correct, the first thing that should come to your mind is cut and paste. This is a very this is almost universally how you prove greedy algorithms to be correct which is you suppose you have some optimal solution which doesn't have the property you want like that it includes E here and then you modify it usually by cutting out one part of the solution and pasting in a different part like E and prove that you still have an optimal solution and therefore there is an optimal solution there is an MST that has the property you Okay, so we're going to do that by starting from an arbitrary uh minimum spanning tree.
So let t star be a minimum spanning tree of G. And if the edge E is in there, we're done. So presumably uh E is not in that minimum spanning tree. We're going to modify t star to include E. So again, let me draw the cut. There's S and V minus S. We have some edge E which crosses the cut, goes from U to V that's not in the minimum spanning tree. Let's say in blue I draw the minimum spanning tree. So you know this minimum spanning tree does it connects everything together here. Uh it's I claim it's got to have some edges uh that cross the cut because if it has no edges that cross the cut, it doesn't connect vertices over here with vertices over here.
So it may not use E, but some of the edges must cross the cut. So here's a possible minimum spanning tree. Uh it happens to have sort of two components over here in S maybe. Who knows? Uh but there's got to be at least one edge that crosses over. In fact, it's uh the minimum spanning tree tar has to connect vertex u to vertex v somehow. Doesn't use e, but there's got to be it's a tree. So in fact, there has to be a unique path from U to V. in the minimum spanning tree. And now U is in S. V is not in S. So if you look at that path for a while, you might stay in S, but eventually you have to leave S, which means there has to be an edge like this one, uh, which I'll call E prime, which transitions from S to V minus S.
So there must be an edge E prime in the minimum spanning tree uh that crosses the cut because U and V are connected by a path and that path starts in S ends not in S. So it's got to transition at least once. It might transition many times but there has to be at least one such edge. And now what I'm going to do is cut and paste. I'm going to remove E prime and add in E instead. So I'm going to look at T star minus minus E prime uh plus E. I claim that is a minimum spanning tree. First I want to claim this is maybe the more annoying part uh that it is a spanning tree. Uh this is more of a graph theory thing.
Um I guess one one comforting thing is that you've preserved the number of edges. So it should still be uh if you get one property, you get the other. Uh because I removed one edge, added one edge, I'm still going to have n minus one edges. The worry I guess is that things become disconnected when you do that. Uh but that's essentially not going to happen because if I think of removing E prime again that disconnects the tree into two parts and I know by this path that one part contains this vertex another part contains this vertex and I know uh that this vertex is connected to U and this vertex is connected to V.
Maybe I should call this U prime and V prime. I know U and U prime are connected by a path. I know V and V prime are connected by a path. But I know that by deleting E prime, U prime and V prime are not connected to each other. Therefore, U and V are not connected to each other after removing E prime. So when I add in E, I newly connect U and V again. And so uh everything's connected back together. I have exactly the right number of edges. Therefore, I'm a spanning tree. Okay, so that's the graph theory part. Now the interesting part from a greedy algorithm is to prove that this is minimum that the weight is not too big.
So let's do that over here. So I have the weight of T star minus E plus minus E prime plus E. By linearity, this is just the weight of T star minus the weight of E prime plus the weight of E. And now we're going to use this property. We haven't used that yet. E is a least weight edge crossing the cut. So E prime crosses the cut. So does E. But E is the smallest possible weight you can have crossing the cut. That means that uh I'll put that over here. The weight of E is less than or equal to the weight of E prime. E prime is a particular edge crossing the cut. E was the smallest weight of them.
So that tells us something about this. uh signs are so difficult. Um I think that means that this is negative or zero right so this should be less than or equal to w of t star and that's what I want because that says the weight of this spanning tree is less than or equal to the optimum weight the minimum weight so that means actually this must be minimum so what I've done is I've constructed a new minimum spanning tree it's just as good as t star But now it includes my edge E and that's what I wanted to prove. There is a minimum spanning tree that contains E provided E is the minimum weight edge crossing and cut.
So that proves this greedy choice property. And I'm going to observe one extra feature of this uh proof which is that uh so we cut and paste in the sense that we removed one thing which was E prime and we added a different thing E and uh a useful feature is that the things that we change only uh are edges that cross the cut. So we only let's say modified edges that cross the cut. I'm going to use that later. We removed one edge across the cut and we put in the one that we wanted. Okay, so far these are a bunch of lemmas. Now we get to use al now we actually get to do algorithms using these lemas.
Um we'll start with maybe the less obvious algorithm. Uh but it's nice because it's very much like dystra follows very closely to the dystra model. Um and then we'll get to the one that we've all been thinking about which is choose a minimum weight edge uh contract and repeat. That doesn't well yeah that does work. Uh but the obvious way is maybe slow. We want to do it in nearlinear time. Let's start with a dystra like algorithm. This is prim's algorithm. Maybe I'll start by writing down the algorithm. It's a little long. Um, in general, the idea we're going to we want to apply this greedy choice property.
To apply the greedy choice property, you need to choose a cut. With prim, we're going to start out with an obvious cut, which is a single vertex. If we have a single vertex S and we say that is our set capital S, then you know there's some edges coming out of it. There's basically S versus everyone else. Um that's a cut. And so I could take the minimum weight edge coming out of that cut and put that in my minimum spanning tree. So when I do that, I put it in my minimum spanning tree because I know it's in some minimum spanning tree. Now I'm going to make s capital S grow a little bit to include that vertex and repeat.
That's actually also a very natural algorithm. Start with a tiny S and just keep growing it one by one. At each stage, use this lema to guarantee the edge I'm adding is still in the minimum spanning tree. So to make that work out, we're always going to need to choose the minimum weight edge that's uh coming out of the uh cut. And we'll do that using a priority Q just like we do in Dystra. So for every uh vertex that's in V minus S uh we're going to have that vertex in the priority Q and the question is what is uh what is the key value of that node stored in the priority Q. So the invariant I'm going to have is that the key of V is the minimum of the weights of the edges.
uh that cross the cut into V. So for vertex V, I want to look at the I'm not going to compute this every time. I'm going to maintain it. I I want that the minimum weight of an edge that starts in S and goes to V, which is not in S because uh V is in Q. Q only stores vertices that are not in S. I want it I want the key value to be that minimum weight. So if I choose the overall minimum vertex that gives me the edge of minimum weight that crosses the cut. Okay, I've sort of divided uh this minimum into vertex by vertex. For every vertex over here, I'm going to say what's the minimum incoming weight from somebody over here?
What's the minimum incoming weight from someone over here to there uh to here? Take the minimum of those things. And of course, the min of all those will be the min of all those edges. Okay, that's how I'm dividing things up and this will be easier to maintain. But let me first initialize everything. Uh, okay. I guess we're going to actually initialize with S being the empty set. So Q will store everybody. Uh, except I'm going to get things started. by setting for particular vertex little S, I'm going to set its key to zero. It doesn't matter who little S is. Uh that's just your start vertex. Just pick one vertex and set its key to zero.
So that will force it to be chosen first because for everyone else for v uh not equal to s I'm going to set the key to infinity because we haven't yet seen any edges that go in there. But we'll change that in a moment. Okay, so that was the initialization. Now we're going to do a loop. We're going to keep going until the Q is empty because uh when the Q is empty, that means S is everybody. And at that point, we'll have a spanning tree on the whole graph and it better be minimum. Okay. And we're going to do that by extracting the minimum from our priority Q. This when we remove Q, uh when we move we remove vertex U from the Q Q.
This means that we're adding U to S. Okay, by taking it out of Q that means it enters S by the invariant at the top. So now we need to update uh this invariant that all the key values are correct. As soon as we move a vertex into S, now there are new edges we have to consider from S to not S. And we do that just by looking at all of the neighbors of U. So this we haven't written this in a long time but this is how it's usually written in dystra except in dystra these are the outgoing edges from u and v are the neighbors here it's an undirected graph so these are all of the neighbors v of you. This is an adjacy list.
Okay. Uh so we're looking at u which has just been added to s and we're looking at the edges. We want to look at the edges that go to V minus S, only those ones. And then for those uh vertices V, we need to update their keys because it used to just count all of these edges that went from the rest of S to V. And now we have a new edge UV that uh V needs to consider because U just got added to S. Okay. And uh so first thing I'm going to say is if V is in Q. So we're just going to store uh a boolean for every vertex about whether it's in the Q. And so when I extract it from the Q, I just set that boolean to false.
Being in the Q is the same as being not in S. This is what Q represents. So Q is over here kind of. So if we're in the queue, same as saying V is not in S, uh then we're going to do a check which lets us compute the minimum. This is going to look a lot like a relaxation. Uh, sorry. Okay, couple things going on because I want to compute not just the value of the minimum spanning tree, I actually want to find the minimum spanning tree. So, I'm going to store parent pointers. Uh, but this is just basically taking a min. I say if the weight of this edge is smaller than what's currently in the key, then update the key because the key is supposed to be the min.
Okay, that's all we need to do to maintain this invariant this for loop. After the for loop, uh this property will be restored. V.key will be that minimum. And furthermore, we kept track of where the minimums came from. Uh so when you end up extracting a vertex, you've already figured out uh which edge you added to put that into the set. So in fact you already had a parent. This would be uh u. And we are basically we want to add that edge into the minim minimum spanning tree when we add U to S. uh overall let me write why this is happening at the end of the algorithm we want for every vertex V we want V.parent and that will be our minimum spanning tree.
Those are the edges that form the minimum spanning tree. Okay, let's prove that this works. Uh, actually, let's do an example. enough curves for a while. Uh, let's do it over here. Need a little break. Examples are fun though. Easy to make mistakes. So, correct me if you see me making a mistake. Uh, let me draw a graph. Okay. Weights. 14 3 8 5 6 12 7 9 15 10. Okay. Uh colors. So uh I've I want to start at this vertex just because it I know it does an interesting thing or it's a nice example. Uh here's my weighted undirected graph. I want to compute minimum spanning tree. I'm going to start with uh capital S being well actually I start with capital S being nothing and all of the weights all of the key values are initially infinity.
So I'm going to write the key values in blue. So initially everything is infinity for every vertex except for s the value is zero. Okay then uh so all of these things are in my priority Q and so when I uh extract from the Q I of course get S. Okay, that's the point of that setup. So, uh, that's when I draw the red circle containing little S. The red circle here is supposed to be capital S. So, uh, at this point, I've added capital S or little S to capital S. And then I look at all of the neighbors V of S and I make sure that they are outside of S. In this case, they all are. All three neighbors, these three guys, um, are not in S.
And then I look at the weights of the edges here. Here I have a weight seven edge that's smaller than infinity. So I'm going to cross out infinity and write seven. And 15 is smaller than infinity. So I'm going to cross out infinity. Write 15. And 10 surprise is smaller than infinity. So I'm going to cross out infinity. Write 10. So now I've I've updated the key values for those three nodes. I should mention in the priority Q to do that that is a decrease key operation. This thing here is a decrease key. You need to update the priority key to say, "Hey, look, the key of this node changed." And so you're going to have to move it around in the heap or whatever.
Just like dystra, same thing happens. Okay, so I've decreased the key of those three nodes. Now I do another iteration. I look at all of the key values stored. The smallest one is seven, right? uh because this node's no longer in there. So I'm going to add this node to capital S. So capital S is going to grow to include that node. I've extracted it from the Q. And now I look at all the neighbors of that node. So for example, here's a neighbor. Uh 9 is less than infinity, so I'll write nine. Here's a neighbor. 12 is less than infinity, so I write 12. Uh five is less than infinity, so I write five.
Here's a neighbor. Uh, but S is in big S. So, we're not going to touch that edge. We're not going to touch S. Okay. We'll end up looking at every edge twice. So, no big deal. All right. Now, who's smallest? Five. I think it's the smallest blue key. Uh, so we're going to add five to the set. Sorry. Add this vertex to the set S. Uh, and then look at all of the outgoing edges from here. Uh, so six is actually less than 12. So this edge is better than that one was. Uh, then what's that? An eight. 8 is less than 10. Uh, 14 is definitely less than infinity. And we look at this edge, but that edge goes, it stays inside the red set, so we forget about it.
uh next smallest value is six, right? So, uh six, we add this guy in. We look at the edges from that vertex, but actually nothing happens because all those vertices are inside capital S. So, we don't look at we don't care about those edges. Next one is uh eight, right? So we'll add in this vertex. And there's only one edge that leaves the cut. So that's three. And three is indeed better than 14. So whoa, never mind. Stop. Uh, so good. Now I think the smallest key is three. Notice smallest key is smaller than anything we've seen before other than zero, but that's okay. just add it in. Uh, and there's no edges leaving the cut from there.
And then over here we have nine and 15. So, first we'll add nine. Uh, there's no edges there. Then we add 15. Okay. Now S is everything. We're done. Q is empty. Uh, where's the minimum spanning tree? I forgot to draw it. So, uh, luckily all of the edges here have different numbers as labels. So, when I have a three here, what I mean is include three in the minimum spanning tree. the edge that was labeled three. Okay, so this will be minimum spanning tree edge. Five will be minimum spanning tree edge. These are the actually the parent pointers. Six will be a minimum spanning tree edge. Uh seven, 9, 15, and eight.
Okay, every vertex except the starting one will have a parent, which means we'll have exactly n minus one edges. That's a good sign. uh and in fact this will be a minimum spanning tree. That's the claim because every time we grew the circle to include a bigger thing, we're guaranteed that this edge was in the minimum spanning tree by applying this property with that cut. Let me just write that down. Okay. To prove correctness, you need to prove an invariant that this key, the key of every vertex always remains this minimum. So this is an invariant. You should prove that by induction. I won't prove it here.
Uh but we have another invariant more interesting one from an MST perspective that's just a sort of algorithm implementation detail uh that the tree uh t subs within s is always contained in a minimum spanning tree of g. So over here uh we have this way of computing minimum spanning tree for all vertices V. But uh what I'd like to do is just look at V that's currently in S. By the end that will be the whole thing. But if I look at V and S and I always look at the edge from V to V.parent that gives me this tree TS I claim it will be contained in a minimum spanning tree of the entire graph. Uh proof by induction.
So uh by induction let's assume induction hypothesis will be that uh let's say there is a minimum spanning tree tar which contains t subs and then what the algorithm does is it repeatedly grows s by adding uh this vertex u to s. So let's suppose that it adds uh u to s. So uh I'm actually going to look at the edge that it adds. So we have S and V minus S and we do this thing like we just saw of growing by one. We add one new vertex over here to S. And that vertex has a parent edge, has a parent pointer. So this edge I'm going to call E. So we're adding some vertex U that we extracted the minimum and we also added an edge E to uh this TS because we grew S by one.
Okay, when I do that, all I do is say, look, greedy choice property guarantees there's a minimum spanning tree that contains E because E because we extracted the min from the Q and the key values are this as I was arguing before that is the minimum overall edge that crosses the cut. E is a minimum weight edge that crosses the cut. And so by greedy choice property uh there is some minimum spanning tree that contains E. But actually I need that the minimum spanning tree not only contains E but also contains all the other uh spanning tree edges that we had already said were in TAR. Okay. So here's where I'm going to use the stronger property.
Um I can modify uh t star to include e and t subs. So we already assume that t star includes t subs. I just don't want to break that. And if you remember the proof of this greedy choice property, we said, well, we all we need to do is remove one edge from the that crosses the cut and replace it with E. So here, what I'm saying is there's some edge. Yeah, maybe there's some edge over here in the in T star that we had to remove and then we put E in. And then we get a minimum spanning tree again. Uh T star prime. Okay. uh this edge that I remove cannot be one of the TS edges because the TS edges are all inside S.
So because I'm only removing an edge that crosses the cut, uh I'm not disturbing TS. TS will remain inside T star and but then I get the new property that E is inside T star and so I prove uh this invariant holds. Okay, I might I keep changing t star, but I always preserve the property that all of the spanning tree edges that are inside S are contained in some minimum spanning tree of G. I'll add in some for emphasis. Cool. So that's how we use the greedy choice property to get uh correctness of Prim's algorithm. What's the running time of Prim's algorithm? same as Dystra. Good answer. Uh I guess it depends what priority queue you use, but whatever priority queue you use is the same as Dystra.
And so in particular if we use Fibonacci heaps which again we're not covering uh we get uh v log v plus e in general uh it is uh for every edge we have to do a decrease key actually for every edge we do two decrease key operations potentially uh if you think about it but uh you know this for loop over the adjacy this is bas the cost of this this stuff is constant the cost of this is the degree of the vertex uh u and so we're basically doing the sum of the degrees of the vertices which um which is the number of edges times two right that's the handshaking lema so for every edge we're potentially doing one decrease key operation and with Fibonacci heaps that's constant time but we're also doing v extract mins those cost log v time because the size of the q is at most v and so that is actually the right running time Just like dystra.
So easy formula to remember. All right, let's do one more algorithm. Cruscll's algorithm. Crosscllow's algorithm is a little bit weirder from the S perspective, I guess. Uh, but we'll see we'll see what cuts we're using in a moment. Uh but it's based around this idea of well the globally minimum weight edge is the minimum weight edge for all cuts that that cross it or for all cuts that it crosses. The globally minimum weight edge is going to be a valid choice. And so by this theorem you pick some S that partitions the end points of E. Uh therefore E is in a minimum spanning tree. So let's choose that one first and then repeat.
Conceptually, what we want to do was that DP idea of contract the vertex, sorry, contract the edge and then find the minimum weight edge that remains. Uh, but the way I'm going to phrase it doesn't explicitly contract, although implicitly it's doing that. And there's a catch. The catch is uh suppose I've you know picked some edges out uh to be in my minimum spanning tree. Suppose this was the minimum weight and this was the next minimum. Next minimum next minimum next minimum. Suppose that the next large at this point after contracting those edges the minimum weight edge is this one. Do I want to put this edge in my minimum spanning tree?
No. that would add a cycle. Cycles are bad. So, I'm going to have this is the tricky part of this algorithm. I have to keep track of uh whether I should actually add an edge. In other words, whether this vertex and this vertex have already been connected to each other. And it turns out you've already seen a data structure to do that. Uh this is what I call union find. And the textbook calls disjoint set data structure. This is in recitation recitation three. So I want to maintain for my MST so far. So I'm adding edges one at a time and I have some tree. Well, it's actually a forest, but I'm still going to call it T.
Um, and I'm going to maintain it in a unionfined structure. disjoint set data structure. Remember this had three operations. Make set, union, and find set. Tell me given an item, which uh which set does it belong to. We're going to use that. The sets are going to be the connected components. So after I've added these edges, these guys, these vertices here will form one connected component. and you know everybody else will just be in its own separate component. So to get started uh I'm not going to have any edges in my tree and so every vertex is in its own connected component. So I represent that by calling make set of v for all for all vertices.
So every vertex lives in its own singleton set. Okay. Uh, now I'd like to do the minimum weight edge and then the next minimum weight edge and the next minimum weight edge. That's also known as sorting. So I'm going to sort E by weight increasing weight. So I get to start with the minimum weight edge. So, uh, now I'm going to do a for loop over the edges, increasing order by weight. Now, uh, I want to know I just I have an edge. It's basically the minimum weight edge among the edges that remain. And so I want to know whether I should add it. I'm going to add it provided the end points of the edge are not in the same connected component.
Uh how can I find out whether two vertices are in the same connected component given this setup? Yeah. Call set twice. Call find set twice and see whether they're equal. Exactly. Good answer. So uh if fine set of u is different from fine set of v. Fine set just returns some identifier. We don't really care what it is as long as it returns the same thing for the same set. So if u and v are in the same set, in other words, they're in the same connected component, then find set will return the same thing for both. But provided they're not equal, then we can add this edge into uh into our tree. So we add E to the set T.
Uh and then we have to represent the fact that we just merge the connected components of U and V. And we do that with a union call. And if you're ever wondering what the heck do we use union fine for, this is the answer. The union find data structure was invented in order to implement Crus's algorithm faster. Okay, in fact, a lot of data structures come from graph algorithms. The the re the reason Fibonacci heaps were invented was because there was Dyster's algorithm. We wanted it to run fast. So same steel here. You just saw it in the reverse order. First you saw union fine. Now union fine you know you can solve in alpha of n time the inverse acrement function super super tiny slow growing function smaller than log log log log log log log um really small but we have this sorting which is kind of annoying.
So the overall running time let's we'll worry about correctness in a moment. We have to sort uh to sort e by weight. Um, so I'll just call that sort of E. Uh, then we have to do some unions. Uh, I guess for every edge potentially we do a union. So I'll call that I'll just write E times alpha of V. Uh, and then we have to do well we also have to do fine sets but same same deal. It's fine set and union cost alpha amortized. So the total cost for doing this for all edges is going to be the number of edges times alpha and then there's like plus v I guess but that's that's smaller if it's a connected graph.
So uh other than the sorting time this algorithm is really good. It's faster. Uh but if you're sorting by an n login algorithm this is not so great. Uh that's that's how it goes. But I think you can reduce this to sorting just v things instead of e things uh with a little bit of effort like doing a select operation. But what when this algorithm is really good is if your weights are integers. If the in if you have weights let's say uh weight uh of e is zero or one or say n to the c for some constant c then I can use radic sort linear time sorting and then this will be linear time and I'm only paying e times alpha.
So if you have reasonably small weights, Kroscll's algorithm is better. Otherwise, I guess um you prefer Prim's algorithm. But either way, uh I actually used this a variation of this algorithm recently. If you want to generate a random spanning tree, then this you can use exactly the same algorithm. You pick a random edge that you haven't picked already. You see, can I add this edge with this test? If you can add it and repeat that will give you a random spanning tree. It generate all spanning trees uniformly uh likely. So that's fun fact useful thing for union find. Let me tell you briefly about correctness.
Again, we've proved correctness with an invariant. Claim that at all times the tree t of edges that we've picked so far is contained in some minimum spanning tree. tar t star is going to change but uh I always want that the edges I've chosen to be inside a minimum spanning tree again we can prove this by induction so assume by induction that this is true so far and then uh suppose that we're adding an edge here so we're converting uh t into t prime which is t union e By this the data structural setup I know that the end points of E U and V are in different connected components. So if I in general what my picture looks like is I have some various connected components.
Maybe there's a single vertex whatever uh I've built a minimum spanning tree for each one. I've built some tree and I actually know that these trees are contained in one global minimum spanning tree. Okay. And now we're looking at an edge that goes from some vertex u in one connected component to some vertex V in a different connected component. This is our edge E. That's our setup. Uh because the union fine data structure maintains connected components. That's another invariant to prove. Uh we're considering adding this edge which connects two different connected components. So uh I want to use the greedy choice property with some s.
What should S be E to cross a cut. So what's a good cut? Yeah. The connected component of U and then everything else. Uh connected component of U and everything else. That would work. Yeah. Which is also the opposite of the connected component containing V. There are many choices that work. Uh I could take basically this cut which is the connected component of U with everything else versus the connected component of V. I could take this cut, which is a connected kimono of you only versus everybody else. Either of those will work. Good. Good curve. All right. Uh so let's say S equals uh the connected component of U or connected component of V.
E crosses that, right? Because it goes it goes from U to V and U's on one side, V is on the other side. uh I I want it to include an entire connected component because when I apply the greedy choice property, I modify t star and I don't want to modify I don't want to delete any of these edges that are already in my connected components that I've already put in there. But if I choose my cut to just be this, uh I know that the edge that I potentially remove will cross this cut, which means it goes between connected components, which means I haven't added that yet to t. So when I do this apply this greedy choice property I'm not deleting anything from t.
Uh everything that was in t is still in t star. So uh that tells me that t prime uh is contained in t star prime. The new t star that I get when I apply this the the cut and paste argument. I modify t- star potentially by removing one edge and putting e in and the edge that I remove was not already in t which means I preserve this part. Uh but I also get that my new edge e is in the minimum spanning tree. And so that's how you prove by induction that at all times the edges that you've chosen so far are in t star. uh actually to to apply the greedy choice property I need not only that E is cut sorry that E crosses the cut I also need that E is the minimum weight edge crossing the cut that's a little more argument to prove um the rough idea is that uh if you forget about the edges we've already dealt with E is the globally minimum weight edge okay but what about the edges we've already dealt with some of them are in the tree um the edges that are in these that are in T, those obviously don't cross the cut.
That's how we designed the cut. The cut was designed not to cross, not to separate any of these connected components. So all the edges that we've added to T, those are okay. Uh they they're not related to the edges that cross this cut. But we may have already considered some lower weight edges that we didn't add to T. If we didn't add an edge to T, that means actually they were in the same set, which means also those are uh use my other color blue. Those are extra edges in here that are inside a connected component. Uh have smaller weight than E, but they're inside the connected component. So again, they're not crossed.
So uh they don't cross the cut rather. So E is basically the first edge that we're considering that crosses this cut because otherwise we would have added that other edge first. So here we're we have to do sort of the greedy argument again considering edges by weight and E is going to be the first edge that crosses this particular cut which is this connected component versus everyone else. So E has to be the minimum weight edge crossing the cut. So the greedy choice property applies. So uh we can put E in the minimum spanning tree and this algorithm is correct. Okay, so we've used that lema a zillion times by now.
Um, that's minimum spanning tree and nearly linear time.