Java Reference
In-Depth Information
Chapter
29
Graph
Implementations
Contents
An Overview of Two Implementations
The Adjacency Matrix
The Adjacency List
Vertices and Edges
Specifying the Class
Vertex
The Inner Class
Edge
Implementing the Class
Vertex
An Implementation of the ADT Graph
Basic Operations
Graph Algorithms
Prerequisites
Chapter
5
Stacks
Chapter
10
Queues, Deques, and Priority Queues
Chapter 12
Lists
Chapter
15
Iterators
Chapter 19
Dictionaries
Chapter 23
Trees
Chapter 28
Graphs
Objectives
After studying this chapter, you should be able to
•
Describe an adjacency matrix
•
Describe an adjacency list
•
Specify and implement the classes that represent the vertices and edges of a graph
•
Implement the ADT graph by using adjacency lists
L
ike the ADTs you have seen previously, graphs have several implementations.
Each implementation must represent the vertices in the graph and the edges between
