Java Reference
In-Depth Information
A graph is a weighted graph if each edge is assigned a weight. Weighted graphs have
many practical applications.
Key
Point
Figure 28.1 assumes that the graph represents the number of flights among cities. You
can apply the BFS to find the fewest number of flights between two cities. Assume that
the edges represent the driving distances among the cities as shown in Figure 29.1. How
do you find the minimal total distances for connecting all cities? How do you find the
shortest path between two cities? This chapter will address these questions. The former
is known as the
minimum spanning tree (MST) problem
and the latter as the
shortest path
problem
.
problem
Seattle (0)
2097
Boston (6)
983
Chicago (5)
1331
214
807
1003
787
New York (7)
Denver (3)
1260
533
1267
599
San Francisco (1)
1015
888
Kansas City (4)
381
1663
864
Los Angeles (2)
496
1435
Atlanta (8)
781
810
Dallas (10)
239
661
Houston (11)
1187
Miami (9)
F
IGURE
29.1
The graph models the distances among the cities.
The preceding chapter introduced the concept of graphs. You learned how to represent
edges using edge arrays, edge lists, adjacency matrices, and adjacency lists, and how to model
a graph using the
Graph
interface, the
AbstractGraph
class, and the
UnweightedGraph
class. The preceding chapter also introduced two important techniques for traversing graphs:
depth-first search and breadth-first search, and applied traversal to solve practical prob-
lems. This chapter will introduce weighted graphs. You will learn the algorithm for finding
a minimum spanning tree in Section 29.4 and the algorithm for finding shortest paths in
Section 29.5.
Pedagogical Note
Before we introduce the algorithms and applications for weighted graphs, it is helpful to
get acquainted with weighted graphs using the GUI interactive tool at
www.cs.armstrong
.edu/liang/animation/WeightedGraphLearningTool.html
,
as shown in Figure 29.2. The tool
allows you to enter vertices, specify edges and their weights, view the graph, and find
an MST and all shortest paths from a single source, as shown in Figure 29.2.
weighted graph learning tool
on Companion Website
Search WWH ::
Custom Search