O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 13. Graph Algorithms

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required