So, before we can develop code for our implementations we need to settle on an API for edge weighted graphs. Now this actually needs a bit of discussion. It would seem to be simple to add weights. But there's a few technicalities that it's easy to understand. But it's going to take a little explanation. So, the whole idea is that we need an edge abstraction. Before for directed graphs, undirected graphs, we're talking about graphs in terms of connections, and the edges were really implicit. So, for a vertex, we would keep a bag of vertices that its connected to but we wouldn't explicitly represent edges. For weighted edges, we're going to need to do that. So we're going to start out with an the just for processing edges. Now, it's simple. The constructor is just going to create an edge. So, what is an edge? A weighted edge is two vertices that they connect, that, it connects and then a double value, which is the weight. So that's clearly one thing we have to do is, is construct the edge. Now what do we want to do when we process two edges, so that is, we want to compare the weights in, in a typical compare and return a negative value of less than zero if equal and a positive value of one just like any other compare. So we have one the method that takes an edge as argument and compares that edge to this edge for sure. We want to be able to extract the weight and have a string representation of the edge. But then, what about getting the vertices out of the edge? Well, the fact is that the, usually in the, in the algorithm, we're holding on, to a vertex. And generally, what we want to do is get the other vertex. So, if we have a vertex v that we're holding on to, what we want is the other vertex. So well that's the way that will get the vertex to that a given edge. We're on a vertex and we have an edge we want to get the edge that, that, the vertex that, that connects to, We just call the other method. And if we have an idiom, we're just getting started then, then we are happy to take either vertex. So we have either and other for getting the vertices out of the edges and we almost always do this kind of idiom where we pick out and we, we have an edge e that we have to process. We pick out either edge, and we put that in v, And we pick out the other edge, and put that in w. So that's just a, a code for getting us the v and w without adopting some convention on how to use those names that might be required if you tried to access the instance variables directly or through gutter methods. So, that's the edge API. So it's easy to implement. So, now we're going to have instance variables for v and w in the weight. The constructor just sets those instance variables. Either just returns v arbitrarily ag, then other, given a vertex that vertex is v, V or returns w, otherwise, it turns v, so that's easy. And then, compared to is straightforward, just using the weight instance variable of this, which is the keyword referring to this object and that which is the argument edge that we're given. So, that's a complete implementation of the weighted edge API and now our MST algorithms can be clients of that. So well first, first we need a graph API that has weighted edges. So we're going to use edge-weighted graph. And it's going to have the same characteristics of the graph and undirected graph API that we articulated before. So we're going to create empty graph with a certain number of vertices and we do that so we can use vertex index arrays as internal data structures. We'll have a created a weighted graph from an input stream then the main operation to build graphs is just to add edges. And then the key operation that all the algorithms want to perform as usual is uniterable but give all the edges adjacent to a given vertex. So now, we want the edges themselves cuz they have the weights. Not just the vertex that it's connected to. So, this, with the edge API, the edge abstraction we get the edge, which gives us the weight and the other vertex at the same time. Since we're using edges as distinct entities it's easy to allow self loops in parallel edges in the graph API and it doesn't have any impact on the MST algorithms. So, we'll go ahead and do that. How do we represent edge-weighted graphs? I, well, it's the straightforward extension of what we did for undirected graphs. We're going to maintain a vertex index array of edge lists. So for every vertex we have a list of the edges connected to that vertex. For example in this graph weighted graph, there is an edge the ones connected to vertex zero, or an edge that connects and six and zero and has a weight 0.58 and an edge that connects two and zero and has 0.26, zero and four has 0.38, zero and seven has 0.16. As with our undirected graph representations each edge object is going to appear twice. Once for each vertex that it connects. And it's actually not an object, it's a reference to an object in Java. So, a graph is a vertex index array of bags of edges. Since it's undirected each edge is going to appear twice. So, when we build a graph just as with undirected unweighted graphs we have to add,, If, if we have an edge that connects v and w we have to add that edge to both v and w's adjacency list. Otherwise it's quite similar to R code for graph. We have a bag of edges instead of a bag of integers, which were vertex indices. Constructor builds the bag. And builds the array and then fills the bag associated, associated with each vertex as a new empty bag. And then add, add edge, adds the edge to both v and w's bag. And interval just returns the bag associated with the given vertex and that's all the edges that are incident on that vertex. And that's a bag which is interval. So, again, as for all the algorithms that we've been looking at, the clients will just iterate. Usually, you have a vertex, and it'll iterate through the edges adjacent to that vertex. So that's the representation of the graph. What about representing the MST? Well, usually the client of an MST algorithm is going to want to have us compute the MST for a given edge-weighted graph. So, we'll just do that in a class named MST and make that the constructor. So then, as usual, in our graph processing paradigm, the constructor will do all the work. And then the client can ask queries about what happened. And in this case, what's relevant is, what are the edges in the MST? And the MST client is just going to want to iterate through those edges. It might also want the total weight of the MST, so we can provide that, too. So for example if we take a, an example with our tiny edge-weighted graph, We're going to have the number of vertices, the number of edges and then, a list of vertex pairs, which are the edge connections and the associated weights. Ahm the what we'll want is the this is the test client is just going to print the edges in the MST the middle-weight edges that connect them all instead the edges on MST and the weight. And this is the code for that test client. So we build an input stream which is given the argument, so that's the filename. and then, we use the constructor from the stream to build an edge-weighted graph. Then we do an MST calling the MST constructor with that graph is an argument that creates an MST. And then, we use the iterator. That mst.edges will give us some interval set of the edges that are in the MST that it computed in the constructor. And it will print out the edges using two-string for edge and then print out the weight. So that's the code that gives the test client for this MST API. So, for that graph, we get that output with that code. So, that's a, the quick introduction to the API, APIs we use for MSTs.