Data Structures and Algorithms in C++, Second Edition

Chapter 13. Graph Algorithms

Contents

13.1 Graphs	594
13.1.1 The Graph ADT	599
13.2 Data Structures for Graphs	600
13.2.1 The Edge List Structure	600
13.2.2 The Adjacency List Structure	603
13.2.3 The Adjacency Matrix Structure	605
13.3 Graph Traversals	607
13.3.1 Depth-First Search	607
13.3.2 Implementing Depth-First Search	611
13.3.3 A Generic DFS Implementation in C++	613
13.3.4 Polymorphic Objects and Decorator Values *	621
13.3.5 Breadth-First Search	623
13.4 Directed Graphs	626
13.4.1 Traversing a Digraph	628
13.4.2 Transitive Closure	630
13.4.3 Directed Acyclic Graphs	633
13.5 Shortest Paths	637
13.5.1 Weighted Graphs	637
13.5.2 Dijkstra's Algorithm	639
13.6 Minimum Spanning Trees	645
13.6.1 Kruskal's Algorithm	647
13.6.2 The Prim-Jarník Algorithm	651
13.7 Exercises	654

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. 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. Graphs have applications in a host of different domains, including mapping, transportation, electrical engineering, and computer networks.

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 ...