Data Structures and Algorithms in Java, 6th Edition

Chapter 14

Graph Algorithms

Contents

14.1 Graphs

14.1.1 The Graph ADT

14.2 Data Structures for Graphs

14.2.1 Edge List Structure

14.2.2 Adjacency List Structure

14.2.3 Adjacency Map Structure

14.2.4 Adjacency Matrix Structure

14.2.5 Java Implementation

14.3 Graph Traversals

14.3.1 Depth-First Search

14.3.2 DFS Implementation and Extensions

14.3.3 Breadth-First Search

14.4 Transitive Closure

14.5 Directed Acyclic Graphs

14.5.1 Topological Ordering

14.6 Shortest Paths

14.6.1 Weighted Graphs

14.6.2 Dijkstra's Algorithm

14.7 Minimum Spanning Trees

14.7.1 Prim-Jarník Algorithm

14.7.2 Kruskal's Algorithm

14.7.3 Disjoint Partitions and Union-Find Structures

14.8 Exercises

14.1 Graphs

A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them, called edges. Graphs have applications in modeling many domains, including mapping, transportation, computer networks, and electrical engineering. By the way, this notion of a “graph” should not be confused with bar charts and function plots, as these kinds of “graphs” are unrelated to the topic of this chapter.

Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges. Thus, a graph is a way of representing connections or relationships between ...