A weighted edge connects two graph vertices while carrying a comparable value, such as distance or cost. Unlike an unweighted edge, it records both connectivity and information about the connection. section 4.1 section 4.3
The Swift implementation stores endpoint indices and a generic weight W. W must conform to Comparable so edges can be ordered, and to Summable so weights can be added. WeightedEdge compares edges by weight and can reverse itself for an undirected adjacency list. section 4.3 section 4.1
A practical weighted-edge design includes:
- A weight property whose type may be Int, Double, Float, or another Comparable and Summable type. section 4.3
- Endpoint indices u and v, plus a reversed edge carrying the same weight. section 4.3 section 4.1
- A graph neighbor query that returns each neighboring vertex together with its edge weight. section 4.3
Distances in a city network
A graph of U.S. metropolitan areas assigns mile distances to connections, such as Seattle–San Francisco at 678 and Los Angeles–Riverside at 50. These values let Jarník's, or Prim's, algorithm select edges for a minimum spanning tree; the demonstrated network totals 5,372 miles. section 4.3
Figure 4.5. A weighted graph of the 15 largest MSAs in the United States, where each of the weights represents the distance between two MSAs in miles
A weighted graph figure makes the meaning of edge values concrete by displaying distances between metropolitan-area vertices. section 4.3
