Java Reference
In-Depth Information
Chapter
28
Graphs
Contents
Some Examples and Terminology
Road Maps
Airline Routes
Mazes
Course Prerequisites
Trees
Traversals
Breadth-First Traversal
Depth-First Traversal
Topological Order
Paths
Finding a Path
The Shortest Path in an Unweighted Graph
The Shortest Path in a Weighted Graph
Java Interfaces for the ADT Graph
Prerequisites
Chapter
5
Stacks
Chapter
10
Queues, Deques, and Priority Queues
Chapter
23 Trees
Objectives
After studying this chapter, you should be able to
●
Describe the characteristics of a graph, including its vertices, edges, and paths
Give examples of graphs, including those that are undirected, directed, unweighted, and weighted
●
Give examples of vertices that are adjacent and that are not adjacent for both directed and undirected graphs
●
Give examples of paths, simple paths, cycles, and simple cycles
●
Give examples of connected graphs, disconnected graphs, and complete graphs
●
Perform a depth-first traversal and a breadth-first traversal on a given graph
●
List a topological order for the vertices of a directed graph without cycles
●
