JAVA: Implement and test Weighted edge data type
- Implement class Edge (page 610)
- Design and implement a class TestEdge that will find and print the first 5 edges in the tinyEWG file (see page 604 for values)
Page 610
4.3 MINIMUM SPANNING TREES AN edge-weighted graph is a graph model where we associate weights or costs with each edge. Such graphs are natural models for many applications. In an airline map where edges represent flight routes, these weights might represent distances or fares. In an electric circuit where edges represent wires, the weights might represent the length of the wire, its cost, or the time that it takes a signal to propagate through it. Minimizing cost is naturally of interest in such situations. In this section, we consider undirected edge-weighted graph models and examine algorithms for one such problem: tinyEWG. txt V -8 Minimum spanning tree. Given an undirected edge- 16-E weighted graph, find an MST. 4 5 0.35 47 0.37 MST edge 5 7 0.28 (black) 0. 16 Definition. Recall that a spanning tree of a graph is a 5. 0.32 connected subgraph with no cycles that includes all 0.38 the vertices. A minimum spanning tree (MST ) of an 2 3 0.17 17 0.19 edge-weighted graph is a spanning tree whose weight 0 2 0.26 2 0.36 (the sum of the weights of its edges) is no larger than 1 3 0.29 the weight of any other spanning tree. 2 0.34 62 0.40 non-MST edge 3 6 0.52 (gray) 60 0.58 In this section, we examine two classical algorithms for 6 4 0.93 computing MSTs: Prim's algorithm and Kruskal's algorithm. An edge-weighted graph and its MST These algorithms are easy to understand and not difficult to implement. They are among the oldest and most well- known algorithms in this book, and they also take application vertex edge good advantage of modern data structures. Since MSTs have numerous important applications, al- circuit component wire gorithms to solve the problem have been studied at airline airport flight route least since the 1920s, at first in the context of power distribution networks, later in the context of tele- power power plant transmission phone networks. MST algorithms are now impor- distribution lines tant in the design of many types of networks (com- image proximity munication, electrical, hydraulic, computer, road, analysis feature relationship rail, air, and many others) and also in the study of Typical MST applications biological, chemical, and physical networks that are found in nature. 604610 CHAPTER 4 Graphs Weighted edge data type public class Edge implements Comparable
private final int v; // one vertex private final int w; // the other vertex private final double weight; edge weight public Edge(int v, int w, double weight) this . V = v; this . W = w; this . weight = weight; public double weight () { return weight; } public int either() { return v; } public int other(int vertex) if (vertex == v) return w; else if (vertex == w) return v; else throw new RuntimeException ("Inconsistent edge") ; } public int compareTo (Edge that) if (this.weight() that. weight()) return +1; else return 0; public String toString() return String. format ("%d-%d %.2f", v, w, weight); } This data type provides the methods either () and other () so that such clients can use other (v) to find the other vertex when it knows v. When neither vertex is known, our clients use the idiomatic code int v = e.either(), w = e. other(v); to access an Edge e's two vertices
