New topic. we're going to discuss in detail the Minimum Spanning Tree Algorithm, so the minimum spanning tree algorithm was actually discovered. this is found out later, because it was fairly obscure. It was Czech mathematician named Jarnik, and he wrote a paper where he, in effect, had this algorithm in 1930. But engineers and computer scientists attribute the first algorithm that, that uses this method to Prim, who published and rediscovered the algorithm in 1957. We're going to compare this algorithm to, a competitor algorithm that was also discovered roughly at the same time. by the discrete mathematician, computer scientist, Kruskal. So I'm going to explain both algorithms, and you'll get a chance to either implement one or both. They're not completely equivalent. They're equivalent in the sense that they will give you the right answer, but in some circumstance, one could be more efficient than the other but. One doesn't dominate the other completely, and so it's actually useful to have both implemented. Prim's algorithm starts with a single vertex. We could imagine that you pick vertex "a" or. If you're using a C like notation, you have vertex zero, you would start with a single vertex. Look for something that was a minimum weight edge, out of that vertex. And place it in and build your tree. So you would start by saying, let's say, we go to node zero. Look for the minimum weighted edge out of no zero here. What if there is no edge out of node zero? No edge out of node zero, then there's no way for node zero to be connected to the rest of the graph. If there's no connection to the rest of the graph, we don't have a minimal spanning tree. We have what's called. A disjoint or a disconnected graph. So I, you should keep that in mind when you write your algorithm in some instances. The graphs that you'll be looking at will not have a minimum spanning tree, and they need to report that somehow. They need to report that with some other kind of, standard value like some very large maximum integer, or a sentinel value. Maybe it would be negative to indicate that the graph was disconnected, or not a number value. At any case. It is possible, you have a graph, doesn't have to be connected, if it's not connected it won't have a spanning tree. If it is connected namely any vertex can reach any other vertex or any node can reach any other node, then there will be a spanning tree. And if there's a spanning tree there has to be a minimum spanning tree. So Prim builds the spanning tree. One node at a time, connecting the node to the existing tree. So it builds the tree from an existing single component tree. That's going to be the difference between Prim and Kruskal. Later on we'll see with Kruskal that it builds the spanning tree potentially by creating a forest and then as the forest grows out, the forest can connect up. And then you end up with one component. I think the Prim algorithm may be conceptually a little simpler. Okay, so let's quickly go through how Prim is going to pick off edges. I'm going to just draw them conceptually and then keep track of their value. So if the start edge is A. The start node is "A". There are basically two places to get to, "E" and "F". "E" is the one with the shorter distance. So that means I'm going to go from A to E. And as we go, we're building a spanning tree. So we might think of that spanning tree as the existing, or closed set, much like we built A shortest path tree (with Dijkstra) And so we have the existing A, E closed set. And we're looking for what we can reach so that started with a, a value of 2. And the thing we can reach now, as we can go to G which is 4, we can go to D which is 6, we can go to the I which is 4, we can go to the F which is 2. that two is the best. So, let's pick that up that gives us a second value of 2, and now we have we've added F in here, F gives the some other possibilities. That possibility is after I which is 5 but the best of these is one of the fours. We can pie break and we can add that 4 in E to G. And, now we have a new possibility that's that's actually the lowest value which is 3. So we would go along G to H, we have H into our built-up tree, H is 3, we can see that we are picking things off in what's called the "greedy" manner, I want to point that out. This is One of these categories are "greedy" algorithms. Now, we have G to D, H to D which is 5 but the best is one of the things we saw earlier H to I which is 4. And that lets us have an I to D which is also 4, and now we're done. We have six edges, we have a full spanning tree and because we did it in this manner. Here are all its individual costs and if we add them up we get 4, 8, 11, 15, 19. So the total minimum span a tree costs and the Prim method rises to a spanning tree of 19. So repeating for Prim, we start at A. We look for what's the least value edge out of A. That turned out to be, or we could call it the nearest edge. That turned out to be E. And then we keep going from what we built as the set of nodes that are already connected. We pick the next node that's not connected to the existing tree. And we pick the, the smallest edge there, until we have and minus 1 edges, and then that's our result. Or until we don't have, we don't have the ability to select any more. And the, and the graph is disconnected so we can have it disconnected situation. And you can see from how we've structured it, that there's no way we can get loops. We never look back into the pre-existent set of nodes that we've already linked. So, that we, that needs that we'll see in Cresco, we've to also figure out a way to avoid loops. We don't want to, even though there might be a small art. We don't want to end that up with a situation. Where, if we picked, you know, something that was 2 here and something that was 3 here and then we can go on from here or here but this thing was 1, for example. And let's say this was a minimum, we don't pick this one because these two guys were already, were already had that, so we don't look back at the, any of the existing tree. So we just have to keep track of where we haven't yet gone. What are the nodes where we haven't yet gone? If we remember the Dykstra thing, you might call that the Open set. And Closed set might be Existing Tree. So we're [UNKNOWN] a tree, there's an Existing Tree. And we have to look at nearest node that's in the open set, that's another way to think of Prim. Okay, so, now you've seen how to do Prim. You've seen it on graph that should let you be able to do an arbitrary graph. But let me give you a little Quiz, just to check your insight on the algorithm. So, for example, we could have every edge have unit cost, the same cost. And if there was such a graph where every edge was cost 1, and it had 10 nodes and there was indeed a spanning tree, what would the minimum spanning tree cost be? Hopefully you should be able get that. And now, you should be able to generalize it. So, what's the same question if we have an arbitrary sized graph, N? The graph has N nodes, is connected, has unit cost. What would its spanning tree cost be? So think about that. If you remember your mathematical induction you could even make a proof out of this. So anything that would have a connected graph. We would need nine edges in the ten nodes, therefore nine would be the minimum spanning tree cost. And then, in general, if we had N nodes, a spanning tree would have to have N minus 1 edges, and therefore its cost would have to be N minus 1.
