Let's just apply Prim one more time. I need you to be very solid on this because this is the last homework in this first half of the class which is where there'll be a natural break before we end the second half of the course, Take Up Game-Playing. So in order to program this properly, you should always be able to hand simulate. That hand simulation, you're not going to be able to think of your own code, think of its correctness, and implement it properly. So we'll do this one as well. Let's do Prim on it. We're going to start with a again. By the way, is it necessary to start with a? Could I've had started with g or c? Think about that. So I start with a. I can have a goes to h, a goes to b. Clear that it's ab, that's a four. Now, we have the mini-tree, ab. We can go to c, we can go to h, that's 11, that's eight. We have two eights. So we have the possibility of a tie break. Let's do that one. So that is the one that we've already done, but notice we could have tie-breaked and got a to h. Maybe, I'll do a to h after, and see that we get the same result. Now, we have the possibility of an eight, a two, a seven, a four, two is the best. We do a two. Now, I have the possibility of a four or seven. The previous possibility is four is next. Now, I have a seven, another two, two is clearly the best. Now, I have a 10, one is obviously now possible. That's the best. So always keeping track of in the open set, what is our next what are set of choices? Seven is now the best, and the only thing in the open set is e, and we can get the e from f with 10 and from d with nine. So nine is the best. Now, we're done. Let's say at that up, that's 12, 14, 18, 20, 28, 37. So Prim has given us 37. Notice we don't necessarily always get the same one. We could have at the point that we got a to b, we could have gone to h. Let's make sure we get the same thing. So I'm going to redo this. Four again was required. Now, I go to h, that gives us an eight. Now, I can do a one, gives us a one. Now, I can do a two, gives us a two. Now, I can do a four, gives us a four. Now, I can do a two, gives us two. Now, the best is a seven. Now, I do at nine. So that gives us the right number of edges and the same set of clauses before. Notice it gives us a slightly different minimum spanning tree. Nobody said the minimum spanning tree has to be unique, it just means that the cost has to be unique. But there can be many minimum spanning trees with a minimum cost. Okay. Here's pseudocode for Prim. So many places to find the pseudocode. Frequently, pseudocode like this comes from the Wikipedia, and if you're programming, and you shouldn't just be sitting at a terminal and just banging away code, you should be writing at a high-level what you need and pseudocode is a good way to start, have some fairly careful pseudocode that is readily translatable into direct C++ code. So we have a graph G with edges E. The edges are represented in the form of pairs v1 to v2. We are by the way using undirected graphs, we've been using undirected graphs throughout the class. If you want an interesting alternative is to write all the codes, so that you can also work with directed graphs. Recall that undirected graph effectively, when I'll just show you. In a directed graph, you generally say vertex one is connected in this direction to vertex two, and in an undirected graph, you don't have an arrow, and instead that would be the equivalent of two directed edges. So for every edge that was going in one direction, there would be an edge going in the other direction. In the undirect representation, we don't draw the arrows. In the real-world that means every street in your street map is a two-way street. Then we have this basic loop where we're searching for the next smallest distance, and as long as there's the next smallest distance, we add it until we're done with that's the size of the needed number of edges. So after we've established the graph, and set up the fact that we have an empty minimum spanning tree, we start picking distances, and because it's pseudocode, we're not actually showing this, but we're going to have to include something that gets us the shortest edge. We may want to maintain this as a data structure. Sometimes we could have a priority queue, some of you know this idea of edges, and pick off the next smallest edge. So we need some way to get at the next smallest edge. Then we add those in and update and keep going until we're done finding. So say this is just a characterization of Prim and pseudo-code. Prim and Dijkstra called greedy, greedy algorithms are something that work efficiently because they generally have a very simple concept like pick something locally that's best. Greedy algorithms if they work are very good because by picking the best thing locally, you generally have a very cheap computation, and yet knowing that by proof that that gets you the global minimum or maximum lets you have what's called a very highly efficient way. There are lots of greedy algorithms that don't guarantee that you get a global optimum. For example, while we won't study it here, an interesting and difficult and still you might call unsolved problem is the Traveling Salesman Problem. The traveling salesman problem is almost like the minimum spanning tree problem, except that you must produce a spanning tree in a graph that's linear. What I mean by a linear spanning tree, let's say you started with a. The tree structure is going to end up looking like this, with the final node here. If I just go to a next node and a next node, and next node that hasn't been visited in this form, and I choose a minimum, there's no guarantee that the overall path, the overall linear tree, is a minimum. Indeed, what's well-known is that can fail. So this is a very efficient algorithm, but it only finds an approximation, a heuristic approximation to the traveling salesman problem. The traveling salesman problem is an NP complete problem. So the deep suspicion is that there is no polynomial time algorithm on a normal computer that can always solve the traveling salesman problem. So it remains very interesting to try and design things that work very well that are both efficient and either give you an optimum or near optimum solution. So that's a problem I've studied, for example, in my own research. Maybe some of you will want to do that as something optional.
