Data Structures and the Java Collections Framework, Third Edition

CHAPTER 15

Graphs, Trees, and Networks

There are many situations in which we want to study the relationship between objects. For example, in Facebook, the objects are individuals and the relationship is based on friendship. In a curriculum, the objects are courses and the relationship is based on prerequisites. In airline travel, the objects are cities; two cities are related if there is a flight between them. It is visually appealing to describe such situations graphically, with points (called vertices) representing the objects and lines (called edges) representing the relationships. In this chapter, we will introduce several collections based on vertices and edges. Finally, we will design, test, and implement one of those collections in a class, Network, from which the other structures can be defined as subclasses. That class uses several classes— TreeMap, PriorityQueue, and LinkedList —that are in the Java Collections Framework. But neither the Network class nor the subclasses are currently part of the Java Collections Framework.

CHAPTER OBJECTIVES

1. Define the terms graph and tree for both directed/undirected and weighted/unweighted collections.
2. Compare breadth-first iterators and depth-first iterators.
3. Understand Prim's greedy algorithm for finding a minimum-cost spanning tree and Dijkstra's greedy algorithm for finding the minimum-cost path between vertices.
4. Be able to find critical paths in a project network.
5. Be able to utilize, expand, and extend the Network class.