14. Weighted Graphs

In the preceding chapter we saw that a graph’s edges can have direction. In this chapter we’ll explore another edge feature: weight. For example, if vertices in a weighted graph represent cities, the weight of the edges might represent distances between the cities, or costs to fly between them, or the number of automobile trips made annually between them (a figure of interest to highway engineers).

When we include weight as a feature of a graph’s edges, some interesting and complex questions arise. What is the minimum spanning tree for a weighted graph? What is ...

Get Data Structures and Algorithms in Java, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.