Java Reference
In-Depth Information
11
Graphs
Graphs provide the ultimate in data structure flexibility. Graphs can model both
real-world systems and abstract problems, so they are used in hundreds of applica-
tions. Here is a small sampling of the range of problems that graphs are routinely
applied to.
1. Modeling connectivity in computer and communications networks.
2. Representing a map as a set of locations with distances between locations;
used to compute shortest routes between locations.
3. Modeling flow capacities in transportation networks.
4. Finding a path from a starting condition to a goal condition; for example, in
artificial intelligence problem solving.
5. Modeling computer algorithms, showing transitions from one program state
to another.
6. Finding an acceptable order for finishing subtasks in a complex activity, such
as constructing large buildings.
7. Modeling relationships such as family trees, business or military organiza-
tions, and scientific taxonomies.
We begin in Section 11.1 with some basic graph terminology and then define
two fundamental representations for graphs, the adjacency matrix and adjacency
list. Section 11.2 presents a graph ADT and simple implementations based on the
adjacency matrix and adjacency list. Section 11.3 presents the two most commonly
used graph traversal algorithms, called depth-first and breadth-first search, with
application to topological sorting. Section 11.4 presents algorithms for solving
some problems related to finding shortest routes in a graph. Finally, Section 11.5
presents algorithms for finding the minimum-cost spanning tree, useful for deter-
mining lowest-cost connectivity in a network. Besides being useful and interesting
in their own right, these algorithms illustrate the use of some data structures pre-
sented in earlier chapters.
371
